Lower bounds for integral functionals generated by bipartite graphs

Kaskosz, Barbara ; Thoma, Lubos

Czechoslovak Mathematical Journal, Tome 69 (2019) no. 2, pp. 571-592

Abstract (VO)

We study lower estimates for integral fuctionals for which the structure of the integrand is defined by a graph, in particular, by a bipartite graph. Functionals of such kind appear in statistical mechanics and quantum chemistry in the context of Mayer's transformation and Mayer's cluster integrals. Integral functionals generated by graphs play an important role in the theory of graph limits. Specific kind of functionals generated by bipartite graphs are at the center of the famous and much studied Sidorenko's conjecture, where a certain lower bound is conjectured to hold for every bipartite graph. In the present paper we work with functionals more general and lower bounds significantly sharper than those in Sidorenko's conjecture. In his 1991 seminal paper, Sidorenko proved such sharper bounds for several classes of bipartite graphs. To obtain his result he used a certain way of ``gluing'' graphs. We prove his inequality for a new class of bipartite graphs by defining a different type of gluing.

Détail

DOI : 10.21136/CMJ.2019.0453-17

Classification : 05C35, 26D15
Keywords: integral inequality; bipartite graph; graph homomorphism; Sidorenko's conjecture

Bibliographie

[1] Bernardi, O.: Solution to a combinatorial puzzle arising from Mayer's theory of cluster integrals. Sémin. Lothar. Comb. 59 (2007), Article No. B59e, 10 pages. | MR | JFM

[2] Bogachev, V. I.: Measure Theory. Vol. I, II. Springer, Berlin (2007). | DOI | MR | JFM

[3] Conlon, D., Fox, J., Sudakov, B.: An approximate version of Sidorenko's conjecture. Geom. Funct. Anal. 20 (2010), 1354-1366. | DOI | MR | JFM

[4] Conlon, D., Kim, J. H., Lee, C., Lee, J.: Some advances on Sidorenko's conjecture. J. London Math. Soc. 98 (2018), 593-608. | DOI | MR | JFM

[5] Conlon, D., Lee, J.: Finite reflection groups and graph norms. Adv. Math. 315 (2017), 130-165. | DOI | MR | JFM

[6] Hatami, H.: Graph norms and Sidorenko's conjecture. Isr. J. Math. 175 (2010), 125-150. | DOI | MR | JFM

[7] Kaouche, A., Labelle, G.: Mayer and Ree-Hoover weights, graph invariants and bipartite complete graphs. P.U.M.A., Pure Math. Appl. 24 (2013), 19-29. | MR | JFM

[8] Kim, J. H., Lee, C., Lee, J.: Two approaches to Sidorenko's conjecture. Trans. Am. Math. Soc. 368 (2016), 5057-5074. | DOI | MR | JFM

[9] Král', D., Martins, T. L., Pach, P. P., Wrochna, M.: The step Sidorenko property and non-norming edge-transitive graphs. Available at | arXiv | MR

[10] Labelle, G., Leroux, P., Ducharme, M. G.: Graph weights arising from Mayer's theory of cluster integrals. Sémin. Lothar. Comb. 54 (2005), Article No. B54m, 40 pages. | MR | JFM

[11] Li, J. L., Szegedy, B.: On the logarithmic calculus and Sidorenko's conjecture. Available at | arXiv

[12] Lovász, L.: Large Networks and Graph Limits. Colloquium Publications 60. American Mathematical Society, Providence (2012). | DOI | MR | JFM

[13] Mayer, J. E., Mayer, M. Göppert: Statistical Mechanics. J. Wiley and Sons, New York (1940),\99999JFM99999 66.1175.01. | MR

[14] Royden, H. L.: Real Analysis. Macmillan Publishing, New York (1988). | MR | JFM

[15] Sidorenko, A. F.: Inequalities for functionals generated by bipartite graphs. Discrete Math. Appl. 2 (1991), Article No. 489-504 English. Russian original translation from Diskretn. Mat. 3 1991 50-65. | DOI | MR | JFM

[16] Sidorenko, A.: A correlation inequality for bipartite graphs. Graphs Comb. 9 (1993), 201-204. | DOI | MR | JFM

[17] Szegedy, B.: An information theoretic approach to Sidorenko's conjecture. Available at | arXiv