SPEAKER: Hamed Hatami, School of
Computer Science, McGill
TITLE: Elementary asymptotic extremal graph theory is
The purpose of this talk is to show that even the most
elementary problems in asymptotic extremal graph theory can be highly
non-trivial. We study linear inequalities between graph homomorphism densities.
It is known that every such inequality follows from an infinite number of
certain applications of the Cauchy-Schwarz inequality. Lovasz and, in a
slightly different formulation, Razborov asked whether it is true or not that
every algebraic inequality between the homomorphism densities follows from a
"finite" number of applications of the Cauchy-Schwarz inequality. In
this talk, we show that the answer to this question is negative by showing that
the problem of determining the validity of a linear inequality between
homomorphism densities is undecidable.
This talk is based on a joint work with Sergey Norin.