Fall 2013

Undecidability of Linear Inequalities Between Graph Homomorphism Densities

Wednesday, Dec. 4, 2013 10:45 am11:30 am PST

Add to Calendar

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.