Discrete Mathematics and Optimization Seminar
Feb. 7th, 2011
The semidefinite method in extremal graph theory
Sergey Norin
Abstract: 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. We will mention a few of the results obtained in this way in joint work with Hatami, Hladky, Kral and Razborov, answering questions of Erdos, and of Jagger, Stovicek and Thomason.