Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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
Published electronically: December 18, 2015
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Sidorenko's conjecture states that for every bipartite graph $ H$ on $ \{1,\cdots ,k\}$

$\displaystyle \int \prod _{(i,j)\in E(H)} h(x_i, y_j) d\mu ^{\vert V(H)\vert} \ge \left ( \int h(x,y) \,d\mu ^2 \right )^{\vert E(H)\vert}$      

holds, where $ \mu $ is the Lebesgue measure on $ [0,1]$ and $ h$ is a bounded, non-negative, symmetric, measurable function on $ [0,1]^2$. An equivalent discrete form of the conjecture is that the number of homomorphisms from a bipartite graph $ H$ to a graph $ G$ is asymptotically at least the expected number of homomorphisms from $ H$ to the Erdős-Rényi random graph with the same expected edge density as $ G$. In this paper, we present two approaches to the conjecture. First, we introduce the notion of tree-arrangeability, where a bipartite graph $ H$ with bipartition $ A \cup B$ is tree-arrangeable if neighborhoods of vertices in $ A$ 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 $ a_1, a_2$ in $ A$ such that each vertex $ a \in A$ satisfies $ N(a) \subseteq N(a_1)$ or $ N(a) \subseteq N(a_2)$, and also implies a recent result of Conlon, Fox, and Sudakov (2010). Second, if $ T$ is a tree and $ H$ is a bipartite graph satisfying Sidorenko's conjecture, then it is shown that the Cartesian product $ T \tiny {\, \square \,} H$ of $ T$ and $ H$ also satisfies Sidorenko's conjecture. This result implies that, for all $ d \ge 2$, the $ d$-dimensional grid with arbitrary side lengths satisfies Sidorenko's conjecture.

References [Enhancements On Off] (What's this?)

Similar Articles

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

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

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

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