Equalization with a controlled exceptional set
ID: equalization-with-a-controlled-exceptional-set
In a proof of the Szemerédi regularity lemma, suppose equal classes have size and witness splitting creates at most atoms per class. Divide every atom into blocks of size , putting leftovers into the exceptional set. At most vertices are lost. When , at most blocks remain. For equitable regularity energy defined by omitting exceptional vertices, the loss from discarding a fraction is at most : 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.
New to topics? Read the docs here!