= Equalization with a controlled exceptional set
In a proof of the <Szemerédi regularity lemma>, suppose $k$ equal classes have size $L$ and witness splitting creates at most $2^k$ atoms per class. Divide every atom into blocks of size $\ell=\lfloor L/4^k\rfloor$, putting leftovers into the exceptional set. At most $k2^k\ell\leq kL2^{-k}$ <vertices> are lost. When $L\geq2\cdot4^k$, at most $2k4^k$ blocks remain. For <equitable regularity energy> defined by omitting exceptional <vertices>, the loss from discarding a fraction $r$ is at most $2r$: only ordered pairs incident with discarded <vertices> are removed, and every squared <edge density of a bipartite graph> is at most one. This provides a quantitative way to restore equal class sizes after each energy increment.
Back to article page
