Let $G$ be a bipartite graph with vertex sets $X$ and $Y$ and edge density $\alpha$ (meaning that the number of edges is $\alpha|X||Y|$). Then $$\#\{(x_1,x_2,y_1,y_2)\in X^2\times Y^2: x_1y_1,\ x_2y_1,\ x_2y_2 \in E(G) \}\geq \alpha^3|X|^2|Y|^2.$$
This is the particular case of the famous Sidorenko's conjecture for paths of length 3. Balazs Szegedy used the entropy method to prove all (then) known cases of Sidorenko's conjecture as well as few more. However, the general proof has a lot of abstract language. That is why Tim Gowers provided a more simpler proof for paths of length 3 stripping all the abstract language.
The proof for paths of length 3 can be described as follows: entropy of a probability distribution $p:X\to [0,1]$ on a finite set $X$ is $\sum\limits_{x\in X}p(x)\log_2\frac{1}{p(x)}$. This is maximized for the uniform distribution, when it takes the value $\log_2|X|$. It follows that one way of proving that $|X|\geq m$ is to identify a probability distribution $p$ on $X$ with entropy greater than $\log_2m$. If $G$ is a bipartite graph with vertex sets $X$ and $Y$, then there is a probability distribution on the set of quadruples $(x_1,x_2,y_1,y_2)$ of vertices of $G$ such that $x_1y_1, x_2y_1,x_2y_2$ are all edges, that is not in general uniform and that has very nice properties.
The distribution is easy to describe. You first pick an edge $x_1y_1$ of $G$ uniformly at random (from all the edges of $G$). Having picked $x_1y_1$ then you pick $x_2$ uniformly at random from the neighbours of $y_1$, and having picked $x_2$ you pick $y_2$ uniformly at random from the neighbors of $x_2$. This guarantees that $x_1y_1x_2y_2$ is a path of length $3$ (possibly with repeated vertices, as we need for the statement of Sidorenko's conjecture).
My goal was to understand how the proof works in that case and after some deeps thoughts and hard work I was able to understand the idea of the proof but I have some unclear moments with the formal/rigorous proof.
- Am I right that the sample space is $\Omega=\{(x_1,x_2,y_1,y_2)\in X^2\times Y^2: x_1y_1,\ x_2y_1,\ x_2y_2 \in E(G) \}$?
- As far as I understand, the probability distribution is defined on $\Omega$?
- Then he defines $X_1,X_2,Y_1$ and $Y_2$ be random variables that tell us where $x_1,x_2,y_1$ and $y_2$ are. Am I right that $X_1,X_2:\Omega\to X$ and $Y_1,Y_2:\Omega\to Y$ or not?
- Intuitively I understand the distribution on $\Omega$ but how to write it formally? So it is some function $\mathbb{P}:\Omega\to [0,1]$ and how is $\mathbb{P}[\omega]$ defined for each individual $\omega\in \Omega$?
Following along with the the description, $x_1y_1$ is chosen uniformly among edges with probability $1/e(G)$. Then neighbors $y_2$ of $x_1$ and $x_2$ of $y_1$ are chosen (implicitly independently of each other) with (conditional) probabilities $1/d(x_1)$ and $1/d(y_1)$ respectively. Hence $$ {\Bbb P}(\{(x_1,x_2,y_1,y_2)\}) = \bigl( e(G)\, d(x_1)\, d(y_1) \bigr)^{-1}. $$