Archive for November 18th, 2015

Entropy and Sidorenko’s conjecture — after Szegedy

November 18, 2015

Here is a simple but important fact about bipartite graphs. Let $G$ be a bipartite graph with (finite) vertex sets $X$ and $Y$ and edge density $\alpha$ (meaning that the number of edges is $\alpha |X||Y|$). Now choose $(x_1,x_2)$ uniformly at random from $X^2$ and $(y_1,y_2)$ uniformly at random from $Y^2$. Then the probability that all of $x_1y_1, x_1y_2, x_2y_1$ and $x_2y_2$ are edges is at least $\alpha^4$.

The proof is very simple. For each $x$, let $f_x:Y\to\{0,1\}$ be the characteristic function of the neighbourhood of $x$. That is, $f_x(y)=1$ if $xy$ is an edge and $0$ otherwise. Then $\sum_{x,y}f_x(y)$ is the sum of the degrees of the $x\in X$, which is the number of edges of $G$, which is $\alpha |X||Y|$. If we set $f=\sum_{x\in X}f_x$, then this tells us that $\sum_{y\in Y}f(y)=\alpha|X||Y|$. By the Cauchy-Schwarz inequality, it follows that $\sum_{y\in Y}f(y)^2\geq\alpha^2|X|^2|Y|$.

But by the Cauchy-Schwarz inequality again, $(\sum_{y\in Y}f(y)^2)^2=(\sum_{y\in Y}\sum_{x_1,x_2\in X}f_{x_1}(y)f_{x_2}(y))^2$ $= (\sum_{x_1,x_2\in X}\sum_{y\in Y}f_{x_1}(y)f_{x_2}(y))^2$ $\leq |X|^2\sum_{x_1,x_2\in X}(\sum_{y\in Y}f_{x_1}(y)f_{x_2}(y))^2$ $=|X|^2\sum_{x_1,x_2\in X}\sum_{y_1,y_2\in Y}f_{x_1}(y_1)f_{x_2}(y_1)f_{x_1}(y_2)f_{x_2}(y_2).$
That last expression is $|X|^2$ times the number of quadruples $x_1,x_2,y_1,y_2$ such that all of $x_1y_1, x_1y_2, x_2y_1$ and $x_2y_2$ are edges, and our previous estimate shows that it is at least $\alpha^4|X|^4|Y|^2$. Therefore, the probability that a random such quadruple consists entirely of edges is at least $\alpha^4$, as claimed (since there are $|X|^2|Y|^2$ possible quadruples to choose from). (more…)