A special case of Sidorenko’s conjecture - Entropy Methods in Combinatorics

2 A special case of Sidorenko’s conjecture

Let $G$ be a bipartite graph with vertex sets $X$ and $Y$ (finite) and density $α$ (defined to be $\frac{| E (G) |}{| X | | Y |}$ ). Let $H$ be another (think of it as ‘small’) bipartite graph with vertex sets $U$ and $V$ and $m$ edges.

Now let $ϕ : U \to X$ and $ψ : V \to Y$ be random functions. Say that $(ϕ, ψ)$ is a homomorphism if $ϕ (x) ϕ (y) \in E (G)$ for every $x y \in E (H)$ .

Sidorenko conjectured that: for every $G, H$ , we have

ℙ [(ϕ, ψ) is a homomorphism] \geq α^{m} .

Not hard to prove when $H$ is $K_{r, s}$ . Also not hard to prove when $H$ is $K_{2, 2}$ (use Cauchy Schwarz).

Theorem 2.1. Sidorenko’s conjecture is true if $H$ is a path of length $3$ .

Proof. We want to show that if $G$ is a bipartite graph of density $α$ with vertex sets $X, Y$ of size $m$ and $n$ and we choose $x_{1}, x_{2} \in X$ , $y_{1}, y_{2} \in Y$ independently at random, then

ℙ [x_{1} y_{2}, x_{2} y_{1}, x_{2} y_{2} \in E (G)] \geq α^{3} .

It would be enough to let $P$ be a P3 chosen uniformly at random and show that $H [P] \geq \log (α^{3} m^{2} n^{2})$ .

Instead we shall define a different random variable taking values in the set of all P3s (and then apply maximality).

To do this, let $(X_{1}, Y_{1})$ be a random edge of $G$ (with $X_{1}, \in X$ , $Y_{1} \in Y$ ). Now let $X_{2}$ be a random neighbour of $Y_{1}$ and let $Y_{2}$ be a random neighbour of $X_{2}$ .

It will be enough to prove that

H [X_{1}, Y_{1}, X_{2}, Y_{2}] \geq \log (α^{3} m^{2} n^{2}) .

We can choose $X_{1} Y_{1}$ in three equivalent ways:

(1) Pick an edge uniformly from all edges.
(2) Pick a vertex $x$ with probability proportional to its degree $d (x)$ , and then pick a random neighbour $y$ of $x$ .
(3) Same with $x$ and $y$ exchanged.

It follows that $Y_{1} = y$ with probability $\frac{d (y)}{| E (G) |}$ , so $X_{2} Y_{1}$ is uniform in $E (G)$ , so $X_{2} = x^{'}$ with probability $\frac{d (x^{'})}{| E (G) |}$ , so $X_{2} Y_{2}$ is uniform in $E (G)$ .

Therefore,

\begin{array}{l} H [X_{1}, Y_{1}, X_{2}, Y_{2}] & = H [X_{1}] + H [Y_{1} | X_{1}] + H [X_{2} | X_{1}, Y_{1}] + H [Y_{2} | X_{1}, Y_{1}, X_{2}] \\ = H [X_{1}] + H [Y_{1} | X_{1}] + H [X_{2} | Y_{1}] + H [Y_{2} | X_{2}] \\ = H [X_{1}] + H [X_{1}, Y_{1}] - H [X_{1}] + H [X_{2}, Y_{1}] - H [Y_{1}] + H [Y_{2}, X_{2}] - H [X_{2}] \\ = 3 H [U_{E (G)}] - H [Y_{1}] - H [X_{2}] \\ \geq 3 H [U_{E (G)}] - H [U_{Y}] - H [U_{X}] \\ = 3 \log (α m n) - \log m - \log n \\ = \log (α^{3} m^{2} n^{2}) \end{array}

So we are done my maximality.

Alternative finish (to avoid using $\log$ !):

Let $X^{'}, Y^{'}$ be uniform in $X, Y$ and independent of each other and $X_{1}, Y_{1}, X_{2}, Y_{2}$ . Then:

\begin{array}{l} H [X_{1}, Y_{2}, X_{2}, Y_{2}, X^{'}, Y^{'}] & = H [X_{1}, Y_{1}, X_{2}, Y_{2}] + H [U_{X}] + H [U_{Y}] \\ \geq 3 H [U_{E (G)}] \end{array}

So by maximality,

# P_{3} s \times | X | \times | Y | \geq | E (G) |^{3} . □