Undecidability of linear inequalities in graph homomorphism densities

Hatami, Hamed^1, 2 ; Norine, Serguei¹

¹ Department of Mathematics, Princeton University, Princeton, New Jersey 08544
² School of Computer Science, McGill University, Montréal, Quebec, Canada

Journal of the American Mathematical Society, Tome 24 (2011) no. 2, pp. 547-565

Résumé

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ász (Problem 17 in his manuscript Graph homomorphisms: Open problems) 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.

Détail

DOI : 10.1090/S0894-0347-2010-00687-X

Bibliographie

[1] Bollobã¡S, Bã©La Relations between sets of complete subgraphs 1976 79 84

[2] Erdå‘S, Paul, Lovã¡Sz, Lã¡Szlã³, Spencer, Joel Strong independence of graphcopy functions 1979 165 172

[3] Freedman, Michael, Lovã¡Sz, Lã¡Szlã³, Schrijver, Alexander Reflection positivity, rank connectivity, and homomorphism of graphs J. Amer. Math. Soc. 2007 37 51

[4] Goodman, A. W. On sets of acquaintances and strangers at any party Amer. Math. Monthly 1959 778 783

[5] Hilbert, David Ueber Büschel von binären Formen mit vorgeschriebener Functionaldeterminante Math. Ann. 1888 227 236

[6] Lam, T. Y. Introduction to quadratic forms over fields 2005

[7] Lovã¡Sz, L. Semidefinite programs and combinatorial optimization 2003 137 194

[8] Lovã¡Sz, Lã¡Szlã³, Szegedy, Balã¡Zs Limits of dense graph sequences J. Combin. Theory Ser. B 2006 933 957

[9] Matijaseviä, Ju. V. The Diophantineness of enumerable sets Dokl. Akad. Nauk SSSR 1970 279 282

[10] Prestel, Alexander, Delzell, Charles N. Positive polynomials 2001

[11] Razborov, Alexander A. Flag algebras J. Symbolic Logic 2007 1239 1282

[12] Razborov, Alexander A. On the minimal density of triangles in graphs Combin. Probab. Comput. 2008 603 618

[13] Reznick, Bruce Some concrete aspects of Hilbert’s 17th Problem 2000 251 272

[14] Tarski, Alfred A Decision Method for Elementary Algebra and Geometry 1948

[15] Whitney, Hassler The coloring of graphs Ann. of Math. (2) 1932 688 718