Undecidability of Linear Inequalities Between Graph Homomorphism Densities
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.
Attachment | Size |
---|---|
Undecidability of Linear Inequalities Between Graph Homomorphism Densities (slides) | 977.49 KB |