Undecidability of linear inequalities in graph homomorphism densities
Authors:
Hamed Hatami and Serguei Norine
Journal:
J. Amer. Math. Soc. 24 (2011), 547565
MSC (2010):
Primary 05C25, 05C35, 12L05
Published electronically:
December 3, 2010
MathSciNet review:
2748400
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The purpose of this article is to show that even the most elementary problems in asymptotic extremal graph theory can be highly nontrivial. 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.
 [Art27]
Emil Artin, Über die Zerlegung definiter Funktionen in Quadrate, Abh. Math. Sem. Hamburg 5 (1927), 100115.
 [Bol76]
Béla
Bollobás, Relations between sets of complete subgraphs,
Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen,
Aberdeen, 1975), Congressus Numerantium, No. XV, Utilitas Math., Winnipeg,
Man., 1976, pp. 79–84. MR 0396327
(53 #195)
 [ELS79]
Paul
Erdős, László
Lovász, and Joel
Spencer, Strong independence of graphcopy functions, Graph
theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont.,
1977), Academic Press, New York, 1979, pp. 165–172. MR 538044
(81b:05060)
 [FLS07]
Michael
Freedman, László
Lovász, and Alexander
Schrijver, Reflection positivity, rank
connectivity, and homomorphism of graphs, J.
Amer. Math. Soc. 20 (2007), no. 1, 37–51 (electronic). MR 2257396
(2007h:05153), http://dx.doi.org/10.1090/S0894034706005297
 [Goo59]
A.
W. Goodman, On sets of acquaintances and strangers at any
party, Amer. Math. Monthly 66 (1959), 778–783.
MR
0107610 (21 #6335)
 [Hil88]
David
Hilbert, Ueber Büschel von binären Formen mit
vorgeschriebener Functionaldeterminante, Math. Ann.
33 (1888), no. 2, 227–236 (German). MR
1510539, http://dx.doi.org/10.1007/BF01443853
 [IR95]
Yannis E. Ioannidis and Raghu Ramakrishnan, Containment of conjunctive queries: beyond relations as sets, ACM Trans. Database Syst. 20 (1995), no. 3, 288324.
 [KRar]
Swastik Kopparty and Benjamin Rossman, The homomorphism domination exponent, European J. Combin. (to appear).
 [Lam05]
T.
Y. Lam, Introduction to quadratic forms over fields, Graduate
Studies in Mathematics, vol. 67, American Mathematical Society,
Providence, RI, 2005. MR 2104929
(2005h:11075)
 [Lov03]
L.
Lovász, Semidefinite programs and combinatorial
optimization, Recent advances in algorithms and combinatorics, CMS
Books Math./Ouvrages Math. SMC, vol. 11, Springer, New York, 2003,
pp. 137–194. MR 1952986
(2003k:90046), http://dx.doi.org/10.1007/0387224440_6
 [Lov08]
, Graph homomorphisms: Open problems, manuscript (2008).
 [LS06]
László
Lovász and Balázs
Szegedy, Limits of dense graph sequences, J. Combin. Theory
Ser. B 96 (2006), no. 6, 933–957. MR 2274085
(2007m:05132), http://dx.doi.org/10.1016/j.jctb.2006.05.002
 [LS09]
, Random graphons and a weak positivstellensatz for graphs, arXiv.org:0902.1327 (2009).
 [Mat70]
Ju.
V. Matijasevič, The Diophantineness of enumerable sets,
Dokl. Akad. Nauk SSSR 191 (1970), 279–282 (Russian).
MR
0258744 (41 #3390)
 [PD01]
Alexander
Prestel and Charles
N. Delzell, Positive polynomials, Springer Monographs in
Mathematics, SpringerVerlag, Berlin, 2001. From Hilbert’s 17th
problem to real algebra. MR 1829790
(2002k:13044)
 [Raz07]
Alexander
A. Razborov, Flag algebras, J. Symbolic Logic
72 (2007), no. 4, 1239–1282. MR 2371204
(2008j:03040), http://dx.doi.org/10.2178/jsl/1203350785
 [Raz08a]
, On hypergraphs with forbidden vertex configurations,, manuscript (2008).
 [Raz08b]
Alexander
A. Razborov, On the minimal density of triangles in graphs,
Combin. Probab. Comput. 17 (2008), no. 4,
603–618. MR 2433944
(2009i:05118), http://dx.doi.org/10.1017/S0963548308009085
 [Rez00]
Bruce
Reznick, Some concrete aspects of Hilbert’s 17th
Problem, Real algebraic geometry and ordered structures (Baton Rouge,
LA, 1996), Contemp. Math., vol. 253, Amer. Math. Soc., Providence,
RI, 2000, pp. 251–272. MR 1747589
(2001i:11042), http://dx.doi.org/10.1090/conm/253/03936
 [Tar48]
Alfred
Tarski, A Decision Method for Elementary Algebra and Geometry,
RAND Corporation, Santa Monica, Calif., 1948. MR 0028796
(10,499f)
 [Whi32]
Hassler
Whitney, The coloring of graphs, Ann. of Math. (2)
33 (1932), no. 4, 688–718. MR
1503085, http://dx.doi.org/10.2307/1968214
 [Art27]
 Emil Artin, Über die Zerlegung definiter Funktionen in Quadrate, Abh. Math. Sem. Hamburg 5 (1927), 100115.
 [Bol76]
 Béla Bollobás, Relations between sets of complete subgraphs, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976, pp. 7984. MR 0396327 (53:195)
 [ELS79]
 Paul Erdös, László Lovász, and Joel Spencer, Strong independence of graphcopy functions, Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977), Academic Press, New York, 1979, pp. 165172. MR 538044 (81b:05060)
 [FLS07]
 Michael Freedman, László Lovász, and Alexander Schrijver, Reflection positivity, rank connectivity, and homomorphism of graphs, J. Amer. Math. Soc. 20 (2007), no. 1, 3751 (electronic). MR 2257396 (2007h:05153)
 [Goo59]
 A. W. Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959), 778783. MR 0107610 (21:6335)
 [Hil88]
 David Hilbert, Ueber Büschel von binären Formen mit vorgeschriebener Functionaldeterminante, Math. Ann. 33 (1888), no. 2, 227236. MR 1510539
 [IR95]
 Yannis E. Ioannidis and Raghu Ramakrishnan, Containment of conjunctive queries: beyond relations as sets, ACM Trans. Database Syst. 20 (1995), no. 3, 288324.
 [KRar]
 Swastik Kopparty and Benjamin Rossman, The homomorphism domination exponent, European J. Combin. (to appear).
 [Lam05]
 T. Y. Lam, Introduction to quadratic forms over fields, Graduate Studies in Mathematics, vol. 67, American Mathematical Society, Providence, RI, 2005. MR 2104929 (2005h:11075)
 [Lov03]
 László Lovász, Semidefinite programs and combinatorial optimization, Recent advances in algorithms and combinatorics, CMS Books Math./Ouvrages Math. SMC, vol. 11, Springer, New York, 2003, pp. 137194. MR 1952986 (2003k:90046)
 [Lov08]
 , Graph homomorphisms: Open problems, manuscript (2008).
 [LS06]
 László Lovász and Balázs Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), no. 6, 933957. MR 2274085 (2007m:05132)
 [LS09]
 , Random graphons and a weak positivstellensatz for graphs, arXiv.org:0902.1327 (2009).
 [Mat70]
 Ju. V. Matijasevič, The Diophantineness of enumerable sets, Dokl. Akad. Nauk SSSR 191 (1970), 279282. MR 0258744 (41:3390)
 [PD01]
 Alexander Prestel and Charles N. Delzell, Positive polynomials, Springer Monographs in Mathematics, SpringerVerlag, Berlin, 2001, From Hilbert's 17th problem to real algebra. MR 1829790 (2002k:13044)
 [Raz07]
 Alexander A. Razborov, Flag algebras, J. Symbolic Logic 72 (2007), no. 4, 12391282. MR 2371204 (2008j:03040)
 [Raz08a]
 , On hypergraphs with forbidden vertex configurations,, manuscript (2008).
 [Raz08b]
 , On the minimal density of triangles in graphs, Combin. Probab. Comput. 17 (2008), no. 4, 603618. MR 2433944 (2009i:05118)
 [Rez00]
 Bruce Reznick, Some concrete aspects of Hilbert's 17th Problem, Real algebraic geometry and ordered structures (Baton Rouge, LA, 1996), Contemp. Math., vol. 253, Amer. Math. Soc., Providence, RI, 2000, pp. 251272. MR 1747589 (2001i:11042)
 [Tar48]
 Alfred Tarski, A Decision Method for Elementary Algebra and Geometry, RAND Corporation, Santa Monica, Calif., 1948. MR 0028796 (10,499f)
 [Whi32]
 Hassler Whitney, The coloring of graphs, Ann. of Math. (2) 33 (1932), no. 4, 688718. MR 1503085
Similar Articles
Retrieve articles in Journal of the American Mathematical Society
with MSC (2010):
05C25,
05C35,
12L05
Retrieve articles in all journals
with MSC (2010):
05C25,
05C35,
12L05
Additional Information
Hamed Hatami
Affiliation:
Department of Mathematics, Princeton University, Princeton, New Jersey 08544
Address at time of publication:
School of Computer Science, McGill University, Montréal, Quebec, Canada
Email:
hatami@cs.mcgill.ca
Serguei Norine
Affiliation:
Department of Mathematics, Princeton University, Princeton, New Jersey 08544
Email:
snorin@math.princeton.edu
DOI:
http://dx.doi.org/10.1090/S08940347201000687X
PII:
S 08940347(2010)00687X
Keywords:
Graph homomorphism density,
quantum graph,
decidability,
Artin’s theorem
Received by editor(s):
June 20, 2010
Received by editor(s) in revised form:
August 29, 2010
Published electronically:
December 3, 2010
Additional Notes:
The first author was supported in part by NSERC
The second author was supported in part by NSF under Grant No. DMS0701033
Article copyright:
© Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
