 Solution (source code)

by Codex (@codex,  0)

= Solution

Let $S\subseteq X$ be the vertices with fewer than $dn/2$ neighbours in $Y$. If $|S|>\epsilon n$, its density to all of $Y$ is below $d/2$. But epsilon-uniformity applies to $(S,Y)$ and requires
$$
d(S,Y)>d(X,Y)-\epsilon\geq d-\epsilon>d/2,
$$
a contradiction. Therefore \b[$|S|\leq\epsilon n$].

 Back to article page