×

A path forward: tropicalization in extremal combinatorics. (English) Zbl 1495.05141

Summary: Many important problems in extremal combinatorics can be stated as proving a pure binomial inequality in graph homomorphism numbers, i.e., proving that \[\hom (H_1, G)^{a_1} \cdots \hom (H_k, G)^{a_k} \geq \hom (H_{k + 1}, G)^{a_{k + 1}} \cdots \hom (H_m, G)^{a_m}\] holds for some fixed graphs \(H_1, \ldots, H_m\) and all graphs \(G\). One prominent example is Sidorenko’s conjecture. For a fixed collection of graphs \(\mathcal{U} = \{H_1, \ldots, H_m \}\), the exponent vectors of valid pure binomial inequalities in graphs of \(\mathcal{U}\) form a convex cone. We compute this cone for several families of graphs including complete graphs, even cycles, stars and paths; the latter is the most interesting and intricate case that we compute. In all of these cases, we observe a tantalizing polyhedrality phenomenon: the cone of valid pure binomial inequalities is actually rational polyhedral, and therefore all valid pure binomial inequalities can be generated from the finite collection of exponent vectors of the extreme rays. Using the work of S. Kopparty and B. Rossman [Eur. J. Comb. 32, No. 7, 1097–1114 (2011; Zbl 1229.05211)], we show that the cone of valid inequalities is indeed rational polyhedral when all graphs \(H_i\) are series-parallel and chordal, and we conjecture that polyhedrality holds for any finite collection \(\mathcal{U}\). We demonstrate that the polyhedrality phenomenon also occurs in matroids and simplicial complexes. Our description of the inequalities for paths involves a generalization of the Erdős-Simonovits conjecture recently proved in its original form in [M. Sağlam, “Near log-convexity of measured heat in (discrete) time and consequences”, Preprint, arXiv:1808.06717] and a new family of inequalities not observed previously. We also solve an open problem of Kopparty and Rossman [loc.cit.] on the homomorphism domination exponent of paths. One of our main tools is tropicalization, a well-known technique in complex algebraic geometry, first applied in extremal combinatorics in [G. Blekherman, “Tropicalization of graph profiles”, Preprint, arXiv:2004.05207]. We prove several results about tropicalizations which may be of independent interest.

MSC:

05C35 Extremal problems in graph theory
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05B35 Combinatorial aspects of matroids and geometric lattices
05E45 Combinatorial aspects of simplicial complexes

Citations:

Zbl 1229.05211

References:

[1] Blakley, G. R.; Roy, P., Hölder type inequality for symmetric matrics with nonnegative entries, Proc. Am. Math. Soc., 16, 1244-1245 (1965) · Zbl 0142.27003
[2] Blekherman, G.; Raymond, A., Proof of the Erdős-Simonovits conjecture on walks (2020)
[3] Blekherman, G.; Raymond, A.; Singh, M.; Thomas, R., Tropicalization of graph profiles, Trans. Am. Math. Soc. (2022), in press · Zbl 1496.05085
[4] Conlon, D.; Kim, J. H.; Lee, C.; Lee, J., Some advances on Sidorenko’s conjecture, J. Lond. Math. Soc., 98, 593-608 (2018) · Zbl 1433.05166
[5] Conlon, D.; Lee, J., Sidorenko’s conjecture for blow-ups, Discrete Anal., Article 2 pp. (2021), 13 pp. · Zbl 1473.05141
[6] Dress, A.; Gutman, I., The number of walks in a graph, Appl. Math. Lett., 16, 5, 797-801 (2003) · Zbl 1039.05043
[7] Dell, H.; Grohe, M.; Rattan, G., Lovász meets Weisfeiler and Leman, (45th International Colloquium on Automata, Languages, and Programming. 45th International Colloquium on Automata, Languages, and Programming, LIPIcs. Leibniz Int. Proc. Inform., vol. 107 (2018), Schloss Dagstuhl. Leibniz-Zent. Inform.: Schloss Dagstuhl. Leibniz-Zent. Inform. Wadern), Article 40 pp. · Zbl 1504.05276
[8] Develin, M.; Sturmfels, B., Erratum for: “Tropical convexity”, Doc. Math.. Doc. Math., Doc. Math., 9, 205-206 (2004), (electronic), mr2054977 · Zbl 1054.52004
[9] Erdős, P.; Simonovits, M., Compactness results in extremal graph theory, Combinatorica, 2, 3, 275-283 (1982) · Zbl 0508.05043
[10] Goodman, A. W., On sets of acquaintances and strangers at any party, Am. Math. Mon., 66, 778-783 (1959) · Zbl 0092.01305
[11] Hill, C.; Lamboglia, S.; Simon, F. P., Tropical convex hulls of polyhedral sets (2019), arXiv preprint
[12] Hatami, H.; Norin, S., Undecidability of linear inequalities in graph homomorphism densities, J. Am. Math. Soc., 24, 2, 547-565 (2011) · Zbl 1259.05088
[13] Huh, J.; Schröter, B.; Wang, B., Correlation bounds for fields and matroids, J. Eur. Math. Soc., 24, 1335-1351 (2022) · Zbl 1485.05023
[14] Ioannidis, Y. E.; Ramakrishnan, R., Containment of conjunctive queries: beyond relations as sets, ACM Trans. Database Syst., 20, 3, 288-324 (1995)
[15] Katona, G., A Theorem of Finite Sets (1968), Akadémiai Kiadó and Academic Press · Zbl 0313.05003
[16] Kim, J. H.; Lee, C.; Lee, J., Two approaches to Sidorenko’s conjecture, Trans. Am. Math. Soc., 368, 7, 5057-5074 (2016) · Zbl 1331.05220
[17] Kopparty, S.; Rossman, B., The homomorphism domination exponent, Eur. J. Comb., 32, 7, 1097-1114 (2011) · Zbl 1229.05211
[18] J. Kruskal, The number of simplices in a complex, 1963. · Zbl 0116.35102
[19] Lagarias, J. C.; Mazo, J. E.; Shepp, L. A.; McKay, B. D., An inequality for walks in a graph, SIAM Rev., 26, 4, 580-582 (1984)
[20] London, D., Inequalities in quadratic forms, Duke Math. J., 83, 511-522 (1966) · Zbl 0166.03901
[21] Li, J. L.X.; Szegedy, B., On the logarithmic calculus and Sidorenko’s conjecture (2011)
[22] Mantel, W., Problem 28, Wiskund. Opgav., 10, 60-61 (1907) · JFM 38.0270.01
[23] Mason, J. H., Matroid: unimodal conjectures and Motzkin’s theorem, (Combinatorics (Proceedings for the Conference on Combinatorial Mathematics) (1972)) · Zbl 0469.05001
[24] Mulholland, H. P.; Smith, C. A.B., An inequality arising in genetical theory, Am. Math. Mon., 66, 673-683 (1959) · Zbl 0094.00903
[25] Nikiforov, V., Walks and the spectral radius of graphs, Linear Algebra Appl., 418, 1, 257-268 (2006) · Zbl 1106.05065
[26] Nikiforov, V., The number of cliques in graphs of given order and size, Trans. Am. Math. Soc., 363, 3, 1599-1618 (2011) · Zbl 1231.05129
[27] Razborov, A. A., On the minimal density of triangles in graphs, Comb. Probab. Comput., 17, 4, 603-618 (2008) · Zbl 1170.05036
[28] Reiher, C., The clique density theorem, Ann. Math. (2), 184, 3, 683-707 (2016) · Zbl 1348.05103
[29] Sağlam, M., Near log-convexity of measured heat in (discrete) time and consequences, (59th IEEE Annual Symposium on Foundations of Computer Science. 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018 (2018)), 967-978
[30] Sidorenko, A. F., A correlation inequality for bipartite graphs, Graphs Comb., 9, 201-204 (1993) · Zbl 0777.05096
[31] Szegedy, B., An information theoretic approach to Sidorenko’s conjecture (2014), arXiv preprint
[32] Täubig, H.; Weihmann, J.; Kosub, S.; Hemmecke, R.; Mayr, E. W., Inequalities for the number of walks in graphs, Algorithmica, 66, 4 (2013) · Zbl 1275.05028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.