Asymptotic extremal graph theory is non-trivial

Thursday, September 23, 2010 -
2:30pm to 4:30pm
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 represents a powerful tool for obtaining particular approximate and exact results in asymptotic extremal graph theory. We will mention a couple of results obtained in this way in joint work with Hatami, Hladky and Kral, answering questions of Jagger, Stovicek and Thomason, and of Thomasse.
Sergey Norin
Princeton University
Event Location: 
Fine Hall 224