Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Undecidability of linear inequalities in graph homomorphism densities
HTML articles powered by AMS MathViewer

by Hamed Hatami and Serguei Norine PDF
J. Amer. Math. Soc. 24 (2011), 547-565 Request permission

Abstract:

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.

References
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
  • 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. DMS-0701033
  • © Copyright 2010 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: J. Amer. Math. Soc. 24 (2011), 547-565
  • MSC (2010): Primary 05C25, 05C35, 12L05
  • DOI: https://doi.org/10.1090/S0894-0347-2010-00687-X
  • MathSciNet review: 2748400