Georgia Institute of Technology College of Sciences

We express weight enumerator of each binary linear code as a product. An analogous result was obtain by R. Feynman in the beginning of 60's for the speacial case of the cycle space of the planar graphs.

For relations {R_1,..., R_k} on a finite set D, the {R_1,...,R_k}-CSP is a computational problem specified as follows: Input: a set of constraints C_1, ..., C_m on variables x_1, ..., x_n, where each constraint C_t is of form R_{i_t}(x_{j_{t,1}}, x_{j_{t,2}}, ...) for some i_t in {1, ..., k} Output: decide whether it is possible to assign values from D to all the variables so that all the constraints are satisfied. The CSP problem is boolean when |D|=2. Schaefer gave a sufficient condition on the relations in a boolean CSP problem guaranteeing its polynomial-time solvability, and proved that all other boolean CSP problems are NP-complete. In the planar variant of the problem, we additionally restrict the inputs only to those whose incidence graph (with vertices C_1, ..., C_m, x_1, ..., x_m and edges joining the constraints with their variables) is planar. It is known that the complexities of the planar and general variants of CSP do not always coincide. For example, let NAE={(0,0,1),(0,1,0),(1,0,0),(1,1,0),(1,0,1),(0,1,1)}). Then {NAE}-CSP is NP-complete, while planar {NAE}-CSP is polynomial-time solvable. We give some partial progress towards showing a characterization of the complexity of planar boolean CSP similar to Schaefer's dichotomy theorem.Joint work with Martin Kupec.

Robertson and Seymour proved that graphs are well-quasi-ordered by the minor relation and the weak immersion relation. In other words, given infinitely many graphs, one graph contains another as a minor (or a weak immersion, respectively). Unlike the relation of minor and weak immersion, the topological minor relation does not well-quasi-order graphs in general. However, Robertson conjectured in the late 1980s that for every positive integer k, the topological minor relation well-quasi-orders graphs that do not contain a topological minor isomorphic to the path of length k with each edge duplicated. We will sketch the idea of our recent proof of this conjecture. In addition, we will give a structure theorem for excluding a fixed graph as a topological minor. Such structure theorems were previously obtained by Grohe and Marx and by Dvorak, but we push one of the bounds in their theorems to the optimal value. This improvement is needed for our proof of Robertson's conjecture. This work is joint with Robin Thomas.

Generalized triangle T_r is an r-graph with edges {1,2,…,r}, {1,2,…,r-1, r+1} and {r,r+1, r+2, …,2r-2}. The family \Sigma_r consists of all r-graphs with three edges D_1, D_2, D_3 such that |D_1\cap D_2|=r-1 and D_1\triangle D_2\subset D_3. In 1989 it was conjectured by Frankl and Furedi that ex(n,T_r) = ex(n,\Sigma_r) for large enough n, where ex(n,F) is the Tur\'{a}n function. The conjecture was proven to be true for r=3, 4 by Frankl, Furedi and Pikhurko respectively. We settle the conjecture for r=5,6 and show that extremal graphs are blow-ups of the unique (11, 5, 4) and (12, 6, 5) Steiner systems. The proof is based on a technique for deriving exact results for the Tur\'{a}n function from “local stability" results, which has other applications. This is joint work with Sergey Norin.