Georgia Institute of Technology College of Sciences

Many fundamental theorems in extremal graph theory can be expressed as linear inequalities between homomorphism densities. It is known that every such inequality follows from the positive semi-definiteness of a certain infinite matrix. As an immediate consequence every algebraic inequality between the homomorphism densities 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 exhibiting explicit valid inequalities that do not follow from such proofs. Further, we show that the problem of determining the validity of a linear inequality between homomorphism densities is undecidable. Joint work with Hamed Hatami.