 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2007/a/4/d/solution

Let

S

be the vertices of

X

with fewer than

d ∣ Y ∣/2

neighbours in

Y

. If

∣ S ∣ > ϵ n

, it is a permissible subset in the regularity test, and averaging those degrees gives

d (S, Y) < d /2

. But

d (X, Y) \geq d

, so

∣ d (S, Y) - d (X, Y) ∣ > d /2 > ϵ,

contradicting regularity. Therefore there are at most $ϵ n$ such vertices. The same argument in fact rules out

∣ S ∣ \geq ϵ n

when that threshold is integral and nonzero.

 New to topics? Read the docs here!