= Bipartite four-cycle count
If a <bipartite graph> with parts $X,Y$ has at least $\delta|X||Y|$ <edges>, then the number of ordered tuples $(x_1,x_2,y_1,y_2)\in X^2\times Y^2$ for which every $x_iy_j$ is an edge is at least
$$
\delta^4|X|^2|Y|^2.
$$
Indeed, if $d(x_1,x_2)$ is the number of common neighbours of $x_1,x_2$ in $Y$, two applications of the <Cauchy-Schwarz inequality> give
$$
\sum_{x_1,x_2}d(x_1,x_2)^2
\geq\frac1{|X|^2}\left(\sum_y\deg(y)^2\right)^2
\geq\frac1{|X|^2|Y|^2}\left(\sum_y\deg(y)\right)^4.
$$
Back to article page
