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

An epsilon-uniform partition has disjoint classes $V_0,V_1,\dots ,V_k$ covering the vertex set, with $|V_0|\le ϵ|V(G)|$, equal nonexceptional class sizes $|V_1|=\cdots =|V_k|$, and at most $ϵk^2$ unordered pairs of distinct nonexceptional classes failing epsilon-uniformity. The exceptional set need not have the common size.

Szemerédi regularity lemma states that for every $ϵ>0$ and positive integer $m_0$, there is $M=M(ϵ,m_0)$ such that every sufficiently large finite graph, for example every graph of order at least $M$ after enlarging $M$ if needed, has such a partition with $m_0\le k\le M$. The bound depends only on the accuracy and minimum class count, not on the graph's order.