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.

Articles by others on the same topic (0)

There are currently no matching articles.