For $x_1,x_2\in X$, let $d(x_1,x_2)$ be the number of vertices of $Y$ adjacent to both. The required number $Q$ of ordered quadruples is
$$
Q=\sum_{x_1,x_2\in X}d(x_1,x_2)^2.
$$
The <Cauchy-Schwarz inequality> first gives
$$
Q\geq\frac1{|X|^2}\left(\sum_{x_1,x_2}d(x_1,x_2)\right)^2.
$$
Reverse the order of counting. A vertex $y\in Y$ contributes $\deg(y)^2$ ordered pairs, so a second application of Cauchy-Schwarz and the assumed <edge density of a bipartite graph> give
$$
\sum_{x_1,x_2}d(x_1,x_2)
=\sum_{y\in Y}\deg(y)^2
\geq\frac1{|Y|}\left(\sum_y\deg(y)\right)^2
\geq\delta^2|X|^2|Y|.
$$
Therefore the <bipartite four-cycle count> is
$$
\boxed{Q\geq\delta^4|X|^2|Y|^2.}
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 147 / 1 / i / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/iii/paper-147/1/i/solution