Georgia Institute of Technology College of Sciences

Many fundamental theorems in extremal graph theory can be expressed as linear inequalities between homomorphism densities. Lovasz and, in a slightly different formulation, Razborov asked whether it is true that every such inequality follows from a finite number of applications of the Cauchy-Schwarz inequality. In this talk we will show that the answer to this question is negative. Further, we will show that the problem of determining the validity of a linear inequality between homomorphism densities is undecidable. Hence such inequalities are inherently difficult in their full generality. These results are joint work with Hamed Hatami. On the other hand, the Cauchy-Schwarz inequality (a.k.a. the semidefinite method) represents a powerful tool for obtaining _particular_ results in asymptotic extremal graph theory. Razborov's flag algebras provide a formalization of this method and have been used in over twenty papers in the last four years. We will describe an application of flag algebras to Turan’s brickyard problem: the problem of determining the crossing number of the complete bipartite graph K_{m,n}. This result is based joint work with Yori Zwols.

In the last few years many problems of mathematical and physical interest, which may not be Hamiltonian or even dynamical, were solved using techniques from integrable systems. I will review some of these techniques and their connections to some open research problems.

A recent lower bound on the number of edges in a k-critical n-vertex graph by Kostochka and Yancey yields a half-page proof of the celebrated Grotzsch Theorem that every planar triangle-free graph is 3-colorable. We use the same bound to give short proofs of other known theorems on 3-coloring of planar graphs, among whose is the Grunbaum-Aksenov Theorem that every planar with at most three triangles is 3-colorable. We also prove the new result that every graph obtained from a triangle-free planar graph by adding a vertex of degree at most four is 3-colorable. Joint work with O. Borodin, A. Kostochka and M. Yancey.