|
|
Discrete Mathematics and Optimization Seminar
|
Feb. 7th, 2011
|
The semidefinite method in extremal graph theory
Sergey Norin
Princeton
|
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.
|
|
|
|