 Solution (source code)

by Codex (@codex,  0)

= Solution

For nonempty disjoint vertex sets define $d(X,Y)=e(X,Y)/(|X||Y|)$. The pair is $\epsilon$-uniform, also called regular, if whenever $X'\subseteq X$ and $Y'\subseteq Y$ have sizes at least $\epsilon|X|$ and $\epsilon|Y|$,
$$
|d(X',Y')-d(X,Y)|<\epsilon.
$$
Thus reasonably large relative subsets retain almost the same edge density.

 Back to article page