Skip to main navigation Skip to Content

SPEAKER: Hamed Hatami, School of Computer Science, McGill University

TITLE: Elementary asymptotic extremal graph theory is non-trivial

ABSTRACT:

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.