Asymptotic extremal graph theory is non-trivial

Asymptotic extremal graph theory is non-trivial

-
Sergey Norin, Princeton University
Fine Hall 224

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.