 Energy-increment proof of Szemerédi regularity

Use equitable regularity energy with exceptional vertices retained as singleton cells. The refinement variance identity for regularity energy shows that splitting along an irregular pair's witnesses raises energy by more than ${\epsilon }^4|V_i||V_j|/n^2$. More than $\epsilon k^2$ irregular ordered pairs therefore raise energy by more than ${\epsilon }^5/4$ when the exceptional set occupies at most half the vertices.

For equalization with a controlled exceptional set, cut each of the at most $k{2}^k$ witness atoms into pieces of size $\lfloor L/4^k\rfloor$ and put leftovers into singleton exceptional cells. This is a refinement, so it cannot decrease energy. At most $n{2}^{-k}$ vertices are lost. Start with enough cells that this loss, over $\lceil 4{\epsilon }^{-5}\rceil$ rounds, is at most $\epsilon n/2$; the initial exceptional set uses the other half. The number of cells grows by a bounded recurrence depending only on $\epsilon$ and the prescribed minimum. Energy lies in $[0,1]$, so the process terminates.