 Solution

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

For nonempty disjoint vertex sets define

d (X, Y) = e (X, Y) / (∣ X ∣∣ Y ∣)

. The pair is

ϵ

-uniform, also called regular, if whenever

X^{'} \subseteq X

and

Y^{'} \subseteq Y

have sizes at least

ϵ ∣ X ∣

and

ϵ ∣ Y ∣

∣ d (X^{'}, Y^{'}) - d (X, Y) ∣ < ϵ .

Thus reasonably large relative subsets retain almost the same edge density.

 New to topics? Read the docs here!