Two Approaches to Sidorenko's Conjecture

Abstract

Sidorenko's conjecture states that for every bipartite graph $H$ on $\{1,\cdots ,k\}$, $\int {\prod }_{(i,j)\in E(H)}h(x_i,y_j)d{\mu }^{|V(H)|}\ge {\left(\int h(x,y)d{\mu }^2\right)}^{|E(H)|}$ 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 \cite{CoFoSu}. 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\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.

arXiv comment20 pages, 2 figures