Two Approaches to Sidorenko's Conjecture

By Jeong Han Kim, Choongbum Lee, Joonkyung Lee. 2013

78 citations recorded by the source corpus.

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-Renyi 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 \Box 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.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/26b2836eb71e7c9d4f44f43891e17678e80afb94

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

  1. Joonkyung Lee
  2. David Conlon
  3. A. Sah
  4. Peter Keevash

In Discrete Mathematics and Combinatorics

  1. Joonkyung Lee
  2. David Conlon
  3. A. Sah
  4. Peter Keevash

In Geometry and Topology

  1. Joonkyung Lee
  2. David Conlon
  3. A. Sah
  4. Peter Keevash

Citations in the corpus