= Energy-increment proof of Szemerédi regularity
{title2=$\Delta q>\varepsilon^5/4,\quad \#\text{refinements}<\lceil4\varepsilon^{-5}\rceil$}
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 $\varepsilon^4|V_i||V_j|/n^2$. More than $\varepsilon k^2$ irregular ordered pairs therefore raise energy by more than $\varepsilon^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 $k2^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 $n2^{-k}$ vertices are lost. Start with enough cells that this loss, over $\lceil4\varepsilon^{-5}\rceil$ rounds, is at most $\varepsilon n/2$; the initial exceptional set uses the other half. The number of cells grows by a bounded recurrence depending only on $\varepsilon$ and the prescribed minimum. Energy lies in $[0,1]$, so the process terminates.
Back to article page
