Undecidability of linear inequalities in graph homomorphism densities
By Hamed Hatami, Sergey Norin. 2010
61 citations recorded by the source corpus.
The purpose of this article 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. In the language of quantum graphs the validity of such an inequality is equivalent to the positivity of a corresponding quantum graph. Similar to the setting of polynomials, a quantum graph that can be represented as a sum of squares of labeled quantum graphs is necessarily positive. Lov\'asz asks whether the opposite is also true. We answer this question and also a related question of Razborov in the negative by introducing explicit valid inequalities that do not satisfy the required conditions. Our solution to these problems is based on a reduction from real multivariate polynomials and uses the fact that there are positive polynomials that cannot be expressed as sums of squares of polynomials. It is known that the problem of determining whether a multivariate polynomial is positive is decidable. Hence it is very natural to ask "Is the problem of determining the validity of a linear inequality between homomorphism densities decidable?" We give a negative answer to this question which shows that such inequalities are inherently difficult in their full generality. Furthermore we deduce from this fact that the analogue of Artin's solution to Hilbert's seventeenth problem does not hold in the setting of quantum graphs.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/975c0936e1e9414224b85f3a63929973ace002c7
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
In Geometry and Topology
Citations in the corpus
- The History of Degenerate (Bipartite) Extremal Graph Problems (2013, background): “This conjecture was killed in this strong form – by Hatami and Norine [142] – but proven in a weaker, “approximation-form”. which we shall call the Lazebnik-Ustimenko method but will treat only very superficially in Section 3.6.”
- ON possible Turán densities (2012, background): “Hatami and Norine [25] showed that the question whether a given linear inequality in subgraph densities is always valid is undecidable.”