Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2010 / A / 3 / b / Solution

For disjoint nonempty vertex sets $X,Y$, let $e(X,Y)$ count edges with one endpoint in each. Their density isFor $0<ϵ<1$, the pair is a regular pair of vertex sets if all $X^{\prime }\subseteq X$ and $Y^{\prime }\subseteq Y$ with $|X^{\prime }|\ge ϵ|X|$ and $|Y^{\prime }|\ge ϵ|Y|$ satisfyUsing the convention with a strict bound less than $ϵ$ instead gives the same argument below; the assumed density is strictly larger than $ϵ$.