## 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

- R. Ahlswede and G. O. H. Katona,
*Graphs with maximal number of adjacent pairs of edges*, Acta Math. Acad. Sci. Hungar.**32**(1978), no. 1-2, 97–120. MR**505076**, DOI 10.1007/BF01902206 - Daniele Alessandrini,
*Logarithmic limit sets of real semi-algebraic sets*, Adv. Geom.**13**(2013), no. 1, 155–190. MR**3011539**, DOI 10.1515/advgeom-2012-0020 - Xavier Allamigeon, Stéphane Gaubert, and Mateusz Skomra,
*Tropical spectrahedra*, Discrete Comput. Geom.**63**(2020), no. 3, 507–548. MR**4074332**, DOI 10.1007/s00454-020-00176-1 - Grigoriy Blekherman and Shyamal Patel,
*Threshold graphs maximize homomorphism densities*, arXiv:2002.12117 (2020). - Grigoriy Blekherman, Annie Raymond, Mohit Singh, and Rekha R. Thomas,
*Simple graph density inequalities with no sum of squares proofs*, Combinatorica**40**(2020), no. 4, 455–471. MR**4150878**, DOI 10.1007/s00493-019-4124-y - David Conlon, Jacob Fox, and Benny Sudakov,
*An approximate version of Sidorenko’s conjecture*, Geom. Funct. Anal.**20**(2010), no. 6, 1354–1366. MR**2738996**, DOI 10.1007/s00039-010-0097-0 - David Conlon, Jeong Han Kim, Choongbum Lee, and Joonkyung Lee,
*Some advances on Sidorenko’s conjecture*, J. Lond. Math. Soc. (2)**98**(2018), no. 3, 593–608. MR**3893193**, DOI 10.1112/jlms.12142 - 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-London, 1979, pp. 165–172. MR**538044** - Paul Erdős, László Lovász, and Joel Spencer,
*Strong independence of graphcopy functions*, Graph Theory and Related Topics (1979), pp. 165–172. - Victor Falgas-Ravry and Emil R. Vaughan,
*Applications of the semi-definite method to the Turán density problem for 3-graphs*, Combin. Probab. Comput.**22**(2013), no. 1, 21–54. MR**3002572**, DOI 10.1017/S0963548312000508 - Roman Glebov, Andrzej Grzesik, Ping Hu, Tamas Hubai, Daniel Kral, and Jan Volec,
*Densities of 3-vertex graphs*, arXiv:1610.02446 (2016). - Oded Goldreich, Shafi Goldwasser, and Dana Ron,
*Property testing and its connection to learning and approximation*, J. ACM**45**(1998), no. 4, 653–750. MR**1675099**, DOI 10.1145/285055.285060 - G. H. Hardy, J. E. Littlewood, and G. Pólya,
*Inequalities*, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1988. Reprint of the 1952 edition. MR**944909** - Hamed Hatami, Jan Hladký, Daniel Kráľ, Serguei Norine, and Alexander Razborov,
*On the number of pentagons in triangle-free graphs*, J. Combin. Theory Ser. A**120**(2013), no. 3, 722–732. MR**3007147**, DOI 10.1016/j.jcta.2012.12.008 - Hamed Hatami and Serguei Norine,
*Undecidability of linear inequalities in graph homomorphism densities*, J. Amer. Math. Soc.**24**(2011), no. 2, 547–565. MR**2748400**, DOI 10.1090/S0894-0347-2010-00687-X - Hamed Hatami and Sergey Norin,
*On the boundary of the region defined by homomorphism densities*, J. Comb.**10**(2019), no. 2, 203–219. MR**3912211**, DOI 10.4310/JOC.2019.v10.n2.a1 - Hao Huang, Nati Linial, Humberto Naves, Yuval Peled, and Benny Sudakov,
*On the 3-local profiles of graphs*, J. Graph Theory**76**(2014), no. 3, 236–248. MR**3200287**, DOI 10.1002/jgt.21762 - G. Katona,
*A theorem of finite sets*, Theory of graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 187–207. MR**0290982** - Jeong Han Kim, Choongbum Lee, and Joonkyung Lee,
*Two approaches to Sidorenko’s conjecture*, Trans. Amer. Math. Soc.**368**(2016), no. 7, 5057–5074. MR**3456171**, DOI 10.1090/tran/6487 - Joseph B. Kruskal,
*The number of simplices in a complex*, Mathematical optimization techniques, Univ. California Press, Berkeley, Calif., 1963, pp. 251–278. MR**0154827** - László Lovász,
*Graph homomorphisms: open problems*, 2008. Available at http://web.cs.elte.hu/~lovasz/problems.pdf. - László Lovász,
*Large networks and graph limits*, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. MR**3012035**, DOI 10.1090/coll/060 - László Lovász and Balázs Szegedy,
*Random graphons and a weak Positivstellensatz for graphs*, J. Graph Theory**70**(2012), no. 2, 214–225. MR**2921000**, DOI 10.1002/jgt.20611 - Diane Maclagan and Bernd Sturmfels,
*Introduction to tropical geometry*, Graduate Studies in Mathematics, vol. 161, American Mathematical Society, Providence, RI, 2015. MR**3287221**, DOI 10.1090/gsm/161 - Grigory Mikhalkin,
*Enumerative tropical algebraic geometry in $\Bbb R^2$*, J. Amer. Math. Soc.**18**(2005), no. 2, 313–377. MR**2137980**, DOI 10.1090/S0894-0347-05-00477-7 - Tim Netzer and Andreas Thom,
*Positivstellensätze for quantum multigraphs*, J. Algebra**422**(2015), 504–519. MR**3272089**, DOI 10.1016/j.jalgebra.2014.08.053 - V. Nikiforov,
*The number of cliques in graphs of given order and size*, Trans. Amer. Math. Soc.**363**(2011), no. 3, 1599–1618. MR**2737279**, DOI 10.1090/S0002-9947-2010-05189-X - Aaron Potechin,
*Sum of squares lower bounds from symmetry and a good story*, 10th Innovations in Theoretical Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 124, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019, pp. Art. No. 61, 20. MR**3899855** - Annie Raymond, Mohit Singh, and Rekha R. Thomas,
*Symmetry in Turán sums of squares polynomials from flag algebras*, Algebr. Comb.**1**(2018), no. 2, 249–274. MR**3856524**, DOI 10.5802/alco - Alexander A. Razborov,
*Flag algebras*, J. Symbolic Logic**72**(2007), no. 4, 1239–1282. MR**2371204**, DOI 10.2178/jsl/1203350785 - Alexander A. Razborov,
*On the minimal density of triangles in graphs*, Combin. Probab. Comput.**17**(2008), no. 4, 603–618. MR**2433944**, DOI 10.1017/S0963548308009085 - Alexander A. Razborov,
*On 3-hypergraphs with forbidden 4-vertex configurations*, SIAM J. Discrete Math.**24**(2010), no. 3, 946–963. MR**2680226**, DOI 10.1137/090747476 - Christian Reiher,
*The clique density theorem*, Ann. of Math. (2)**184**(2016), no. 3, 683–707. MR**3549620**, DOI 10.4007/annals.2016.184.3.1 - Balazs Szegedy,
*An information theoretic approach to Sidorenko’s conjecture*, arXiv:1406.6738 (2014). - Josephine Yu,
*Tropicalizing the positive semidefinite cone*, Proc. Amer. Math. Soc.**143**(2015), no. 5, 1891–1895. MR**3314099**, DOI 10.1090/S0002-9939-2014-12428-2

## 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