Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

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.

 

Tropicalization of graph profiles
HTML articles powered by AMS MathViewer

by Grigoriy Blekherman, Annie Raymond, Mohit Singh and Rekha R. Thomas PDF
Trans. Amer. Math. Soc. 375 (2022), 6281-6310 Request permission

Abstract:

A graph profile records all possible densities of a fixed finite set of graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known, and little is known about hypergraph profiles. We introduce the tropicalization of graph and hypergraph profiles. Tropicalization is a well-studied operation in algebraic geometry, which replaces a variety (the set of real or complex solutions to a finite set of algebraic equations) with its “combinatorial shadow”. We prove that the tropicalization of a graph profile is a closed convex cone, which still captures interesting combinatorial information. We explicitly compute these tropicalizations for arbitrary sets of complete and star hypergraphs. We show they are rational polyhedral cones even though the corresponding profiles are not even known to be semialgebraic in some of these cases. We then use tropicalization to prove strong restrictions on the power of the sums of squares method, equivalently Cauchy-Schwarz calculus, to test (which is weaker than certification) the validity of graph density inequalities. In particular, we show that sums of squares cannot test simple binomial graph density inequalities, or even their approximations. Small concrete examples of such inequalities are presented, and include the famous Blakley-Roy inequalities for paths of odd length. As a consequence, these simple inequalities cannot be written as a rational sum of squares of graph densities.
References
Similar Articles
  • Retrieve articles in Transactions of the American Mathematical Society with MSC (2020): 05C35
  • Retrieve articles in all journals with MSC (2020): 05C35
Additional Information
  • Grigoriy Blekherman
  • Affiliation: School of Mathematics, Georgia Institute of Technology, 686 Cherry Street, Atlanta, Georgia 30332
  • MR Author ID: 668861
  • Email: greg@math.gatech.edu
  • Annie Raymond
  • Affiliation: Department of Mathematics and Statistics, Lederle Graduate Research Tower, 1623D, University of Massachusetts Amherst, 710 N. Pleasant Street, Amherst, Massachusetts 01003
  • MR Author ID: 902030
  • Email: raymond@math.umass.edu
  • Mohit Singh
  • Affiliation: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, 755 Ferst Drive, NW, Atlanta, Georgia 30332
  • MR Author ID: 769589
  • ORCID: 0000-0002-0827-233X
  • Email: mohit.singh@isye.gatech.edu
  • Rekha R. Thomas
  • Affiliation: Department of Mathematics, University of Washington, Box 354350, Seattle, Washington 98195
  • MR Author ID: 368009
  • Email: rrthomas@uw.edu
  • Received by editor(s): May 21, 2020
  • Received by editor(s) in revised form: January 19, 2022, and January 19, 2022
  • Published electronically: June 30, 2022
  • Additional Notes: The first author was partially supported by NSF grant DMS-1352073. The second author was partially supported by NSF grant DMS-2054404. The third author was partially supported by NSF grant CCF-1717947. The fourth author was partially supported by NSF grant DMS-1719538.
  • © Copyright 2022 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 375 (2022), 6281-6310
  • MSC (2020): Primary 05C35
  • DOI: https://doi.org/10.1090/tran/8643
  • MathSciNet review: 4474892