Undecidability of Linear Inequalities Between Graph Homomorphism Densities
summary
Proves that deciding whether a linear inequality between graph homomorphism densities holds for all graphs is undecidable. Proof reduces Matiyasevich/Hilbert-10th-style undecidability for integers to densities by encoding integers as densities of the form 1-1/n and by exploiting Razborov’s complete description of the edge vs triangle curve in the achievable region; uses flag-algebra identities, graph limits, and a polynomial construction Q so there is no algorithm that always answers the question.
AI-written summary · about