Czechoslovak Mathematical Journal, Vol. 69, No. 2, pp. 571-592, 2019


Lower bounds for integral functionals generated by bipartite graphs

Barbara Kaskosz, Lubos Thoma

Received September 29, 2017.   Published online February 11, 2019.

Abstract:  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.
Keywords:  integral inequality; bipartite graph; graph homomorphism; Sidorenko's conjecture
Classification MSC:  05C35, 26D15


References:
[1] O. Bernardi: 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 2465401 | Zbl 1193.05012
[2] V. I. Bogachev: Measure Theory. Vol. I, II. Springer, Berlin (2007). DOI 10.1007/978-3-540-34514-5 | MR 2267655 | Zbl 1120.28001
[3] D. Conlon, J. Fox, B. Sudakov: An approximate version of Sidorenko's conjecture. Geom. Funct. Anal. 20 (2010), 1354-1366. DOI 10.1007/s00039-010-0097-0 | MR 2738996 | Zbl 1228.05285
[4] D. Conlon, J. H. Kim, C. Lee, J. Lee: Some advances on Sidorenko's conjecture. J. London Math. Soc. 98 (2018), 593-608. DOI 10.1112/jlms.12142 | Zbl 07000630
[5] D. Conlon, J. Lee: Finite reflection groups and graph norms. Adv. Math. 315 (2017), 130-165. DOI 10.1016/j.aim.2017.05.009 | MR 3667583 | Zbl 1366.05107
[6] H. Hatami: Graph norms and Sidorenko's conjecture. Isr. J. Math. 175 (2010), 125-150. DOI 10.1007/s11856-010-0005-1 | MR 2607540 | Zbl 1227.05183
[7] A. Kaouche, G. Labelle: Mayer and Ree-Hoover weights, graph invariants and bipartite complete graphs. P.U.M.A., Pure Math. Appl. 24 (2013), 19-29. MR 3197094 | Zbl 1313.05019
[8] J. H. Kim, C. Lee, J. Lee: Two approaches to Sidorenko's conjecture. Trans. Am. Math. Soc. 368 (2016), 5057-5074. DOI 10.1090/tran/6487 | MR 3456171 | Zbl 1331.05220
[9] D. Král', T. L. Martins, P. P. Pach, M. Wrochna: The step Sidorenko property and non-norming edge-transitive graphs. Available at https://arxiv.org/abs/1802.05007.
[10] G. Labelle, P. Leroux, M. G. Ducharme: Graph weights arising from Mayer's theory of cluster integrals. Sémin. Lothar. Comb. 54 (2005), Article No. B54m, 40 pages. MR 2341745 | Zbl 1188.82007
[11] J. L. Li, B. Szegedy: On the logarithmic calculus and Sidorenko's conjecture. Available at https://arxiv.org/abs/1107.1153.
[12] L. Lovász: Large Networks and Graph Limits. Colloquium Publications 60. American Mathematical Society, Providence (2012). DOI 10.1090/coll/060 | MR 3012035 | Zbl 1292.05001
[13] J. E. Mayer, M. Göppert Mayer: Statistical Mechanics. J. Wiley and Sons, New York (1940). MR 0674819 | JFM 66.1175.01
[14] H. L. Royden: Real Analysis. Macmillan Publishing, New York (1988). MR 1013117 | Zbl 0704.26006
[15] A. F. Sidorenko: Inequalities for functionals generated by bipartite graphs. Discrete Math. Appl. 2 (1991), Article No. 489-504 (In English. Russian original.); translation from Diskretn. Mat. 3 (1991), 50-65. DOI 10.1515/dma.1992.2.5.489 | MR 1138091 | Zbl 0787.05052
[16] A. Sidorenko: A correlation inequality for bipartite graphs. Graphs Comb. 9 (1993), 201-204. DOI 10.1007/BF02988307 | MR 1225933 | Zbl 0777.05096
[17] B. Szegedy: An information theoretic approach to Sidorenko's conjecture. Available at https://arxiv.org/abs/1406.6738.

Affiliations:   Barbara Kaskosz, Lubos Thoma (corresponding author), Department of Mathematics, 5 Lippitt Road, University of Rhode Island, Kingston, RI 02881, USA, e-mail: bkaskosz@uri.edu, thoma@math.uri.edu


 
PDF available at: