Two approaches to Sidorenko's conjecture

Authors:
Jeong Han Kim, Choongbum Lee and Joonkyung Lee

Journal:
Trans. Amer. Math. Soc. **368** (2016), 5057-5074

MSC (2010):
Primary 05D40, 05C35, 26D15; Secondary 62H20

DOI:
https://doi.org/10.1090/tran/6487

Published electronically:
December 18, 2015

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Sidorenko's conjecture states that for every bipartite graph on

holds, where is the Lebesgue measure on and is a bounded, non-negative, symmetric, measurable function on . An equivalent discrete form of the conjecture is that the number of homomorphisms from a bipartite graph to a graph is asymptotically at least the expected number of homomorphisms from to the Erdős-Rényi random graph with the same expected edge density as . In this paper, we present two approaches to the conjecture. First, we introduce the notion of tree-arrangeability, where a bipartite graph with bipartition is tree-arrangeable if neighborhoods of vertices in have a certain tree-like structure. We show that Sidorenko's conjecture holds for all tree-arrangeable bipartite graphs. In particular, this implies that Sidorenko's conjecture holds if there are two vertices in such that each vertex satisfies or , and also implies a recent result of Conlon, Fox, and Sudakov (2010). Second, if is a tree and is a bipartite graph satisfying Sidorenko's conjecture, then it is shown that the Cartesian product of and also satisfies Sidorenko's conjecture. This result implies that, for all , the -dimensional grid with arbitrary side lengths satisfies Sidorenko's conjecture.

**[1]**Itai Benjamini and Yuval Peres,*A correlation inequality for tree-indexed Markov chains*, Seminar on Stochastic Processes, 1991 (Los Angeles, CA, 1991) Progr. Probab., vol. 29, Birkhäuser Boston, Boston, MA, 1992, pp. 7-14. MR**1172139 (93g:60037)****[2]**G. R. Blakley and Prabir Roy,*A Hölder type inequality for symmetric matrices with nonnegative entries*, Proc. Amer. Math. Soc.**16**(1965), 1244-1245. MR**0184950 (32 #2421)****[3]**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 (2012h:05351)**, https://doi.org/10.1007/s00039-010-0097-0**[4]**R. Daudel, R. Lefebvre, and C. Moser,*Quantum chemistry: Methods and applications*, Interscience Publishers, New York-London, 1959. MR**0128419 (23 #B1462)****[5]**P. Erdős and M. Simonovits,*Cube-supersaturated graphs and related problems*, Progress in graph theory (Waterloo, Ont., 1982) Academic Press, Toronto, ON, 1984, pp. 203-218. MR**776802 (86b:05041)****[6]**P. Erdös and A. H. Stone,*On the structure of linear graphs*, Bull. Amer. Math. Soc.**52**(1946), 1087-1091. MR**0018807 (8,333b)****[7]**C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre,*Correlation inequalities on some partially ordered sets*, Comm. Math. Phys.**22**(1971), 89-103. MR**0309498 (46 #8607)****[8]**Hans-Otto Georgii,*Gibbs measures and phase transitions*, de Gruyter Studies in Mathematics, vol. 9, Walter de Gruyter & Co., Berlin, 1988. MR**956646 (89k:82010)****[9]**Rudolf Halin,*-functions for graphs*, J. Geometry**8**(1976), no. 1-2, 171-186. MR**0444522 (56 #2873)****[10]**Hamed Hatami,*Graph norms and Sidorenko's conjecture*, Israel J. Math.**175**(2010), 125-150. MR**2607540 (2011m:05174)**, https://doi.org/10.1007/s11856-010-0005-1**[11]**David London,*Two inequalities in nonnegative symmetric matrices*, Pacific J. Math.**16**(1966), 515-536. MR**0190153 (32 #7567)****[12]**L. Lovász and M. Simonovits,*On the number of complete subgraphs of a graph. II*, Studies in pure mathematics, Birkhäuser, Basel, 1983, pp. 459-495. MR**820244 (87a:05089)****[13]**H. P. Mulholland and C. A. B. Smith,*An inequality arising in genetical theory*, Amer. Math. Monthly**66**(1959), 673-683. MR**0110721 (22 #1589)****[14]**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 (2012g:05106)**, https://doi.org/10.1090/S0002-9947-2010-05189-X**[15]**Robin Pemantle and Yuval Peres,*Domination between trees and application to an explosion problem*, Ann. Probab.**22**(1994), no. 1, 180-194. MR**1258873 (95a:60148)****[16]**Alexander A. Razborov,*On the minimal density of triangles in graphs*, Combin. Probab. Comput.**17**(2008), no. 4, 603-618. MR**2433944 (2009i:05118)**, https://doi.org/10.1017/S0963548308009085- [17]
C. Reiher,
*The clique density theorem*, arXiv:1212.2454 [math.CO]. **[18]**Neil Robertson and P. D. Seymour,*Graph minors. III. Planar tree-width*, J. Combin. Theory Ser. B**36**(1984), no. 1, 49-64. MR**742386 (86f:05103)**, https://doi.org/10.1016/0095-8956(84)90013-3**[19]**A. F. Sidorenko,*Extremal problems in graph theory and functional-analytic inequalities*, Proceedings of the All-Union seminar on discrete mathematics and its applications (Russian) (Moscow, 1984) Moskov. Gos. Univ., Mekh.-Mat. Fak., Moscow, 1986, pp. 99-105 (Russian). MR**930303 (88m:05053)****[20]**A. F. Sidorenko,*Inequalities for functionals generated by bipartite graphs*, Diskret. Mat.**3**(1991), no. 3, 50-65 (Russian); English transl., Discrete Math. Appl.**2**(1992), no. 5, 489-504. MR**1138091 (92h:05136)**, https://doi.org/10.1515/dma.1992.2.5.489**[21]**Alexander Sidorenko,*A correlation inequality for bipartite graphs*, Graphs Combin.**9**(1993), no. 2, 201-204. MR**1225933 (94b:05177)**, https://doi.org/10.1007/BF02988307**[22]**A. Sidorenko,*An analytic approach to extremal problems for graphs and hypergraphs*, Extremal problems for finite sets (Visegrád, 1991) Bolyai Soc. Math. Stud., vol. 3, János Bolyai Math. Soc., Budapest, 1994, pp. 423-455. MR**1319175 (96i:05091)****[23]**Miklós Simonovits,*Extremal graph problems, degenerate extremal problems, and supersaturated graphs*, Progress in graph theory (Waterloo, Ont., 1982) Academic Press, Toronto, ON, 1984, pp. 419-437. MR**776819 (86k:05070)**- [24]
Stan Z. Li,
*Markov Random Field Modeling in Image Analysis*, Springer (2001). **[25]**George Stell,*Generating functionals and graphs*, Graph Theory and Theoretical Physics, Academic Press, London, 1967, pp. 281-300. MR**0239836 (39 #1193)**- [26]
J. X. Li and B. Szegedy,
*On the logarithmic calculus and Sidorenko's conjecture*, arXiv:1107.1153 [math.CO]. **[27]**Paul Turán,*Eine Extremalaufgabe aus der Graphentheorie*, Mat. Fiz. Lapok**48**(1941), 436-452 (Hungarian, with German summary). MR**0018405 (8,284j)**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2010):
05D40,
05C35,
26D15,
62H20

Retrieve articles in all journals with MSC (2010): 05D40, 05C35, 26D15, 62H20

Additional Information

**Jeong Han Kim**

Affiliation:
School of Computational Sciences, Korea Institute for Advanced Study (KIAS), Seoul, South Korea

Email:
jhkim@kias.re.kr

**Choongbum Lee**

Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139-4307

Email:
cb_lee@math.mit.edu

**Joonkyung Lee**

Affiliation:
Mathematical Institute, University of Oxford, OX2 6GG, United Kingdom

Email:
Joonkyung.Lee@maths.ox.ac.uk

DOI:
https://doi.org/10.1090/tran/6487

Received by editor(s):
November 4, 2013

Received by editor(s) in revised form:
June 5, 2014

Published electronically:
December 18, 2015

Additional Notes:
The first author was supported by the National Research Foundation of Korea (NRF) Grant funded by the Korean Government (MSIP) (NRF-2012R1A2A2A01018585) and KIAS internal Research Fund CG046001. This work was partially carried out while the author was visiting Microsoft Research, Redmond, and Microsoft Research, New England.

The third author was supported by ILJU Foundation of Education and Culture.

Article copyright:
© Copyright 2015
American Mathematical Society