= Solution
An epsilon-uniform partition has disjoint classes $V_0,V_1,\ldots,V_k$ covering the vertex set, with $|V_0|\leq\epsilon|V(G)|$, equal nonexceptional class sizes $|V_1|=\cdots=|V_k|$, and at most $\epsilon 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 $\epsilon>0$ and positive integer $m_0$, there is $M=M(\epsilon,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\leq k\leq M$. The bound depends only on the accuracy and minimum class count, not on the <graph>'s order.
Back to article page
