= Solution
For disjoint nonempty <vertex> <sets> $U,V$, write $d(U,V)=e(U,V)/(|U||V|)$. A <regular pair of vertex sets> is $\varepsilon$-regular if every $U'\subseteq U,V'\subseteq V$ with $|U'|\geq\varepsilon|U|$, $|V'|\geq\varepsilon|V|$ satisfies $|d(U',V')-d(U,V)|\leq\varepsilon$.
The <Szemerédi regularity lemma> states that, for every $\varepsilon>0$ and <integer> $m_0$, there are $M,n_0$ such that every finite simple <graph> on $n\geq n_0$ <vertices> has a <set partition>
$$
V=V_0\sqcup V_1\sqcup\cdots\sqcup V_m
$$
with \b[$m_0\leq m\leq M$, $|V_0|\leq\varepsilon n$, $|V_1|=\cdots=|V_m|$, and at most $\varepsilon m^2$ irregular unordered pairs among the nonexceptional classes]. Prove it for $0<\varepsilon\leq1/2$; larger parameters follow by using a smaller one.
For the <energy-increment proof of Szemerédi regularity>, keep every exceptional <vertex> as a singleton cell in the <set partition> used to measure <regularity energy>. Define the <equitable regularity energy>
$$
q(\mathcal P)=\frac1{n^2}\sum_{U,V\in\mathcal P}|U||V|d(U,V)^2.
$$
The sum is ordered, and on diagonal cells <subset density> means the average of the adjacency indicator, with zero on loops. Thus $0\leq q\leq1$. If $U,V$ are refined into $U_a,V_b$, expanding squares gives
$$
\sum_{a,b}|U_a||V_b|d(U_a,V_b)^2-|U||V|d(U,V)^2=\sum_{a,b}|U_a||V_b|[d(U_a,V_b)-d(U,V)]^2\geq0.
$$
The cross term vanishes because the weighted <arithmetic mean> of the refined <subset densities> is the original <subset density>. Consequently every <refinement of a set partition> increases or preserves <regularity energy>.
Suppose the current nonexceptional classes have common size $t$ and there are $k$ of them. For each <irregular pair> $V_i,V_j$, choose witnesses $A_{ij},B_{ij}$ of sizes at least $\varepsilon t$ and discrepancy greater than $\varepsilon$. Refine each class by all its incident witness <subsets>. There are at most $k-1$ cuts in each class and at most $2^k$ resulting atoms. The witness rectangle is a union of refined rectangles. By the <Cauchy-Schwarz inequality>, its contribution to the <variance> identity is at least
$$
|A_{ij}||B_{ij}|[d(A_{ij},B_{ij})-d(V_i,V_j)]^2>\varepsilon^4t^2.
$$
Indeed, the sum of squared deviations on the witness rectangle is at least its total weight times the square of their weighted <arithmetic mean>. If more than $\varepsilon k^2$ unordered pairs are irregular, summing even just one orientation of each gives
$$
\Delta q>\varepsilon^5\frac{k^2t^2}{n^2}\geq\frac{\varepsilon^5}{4},
$$
provided the exceptional <set> has at most $n/2$ <vertices>. This is the strictly positive <regularity energy> increment.
Restore equal class sizes without losing that increment. Divide every witness atom into blocks of size $\ell=\lfloor t/4^k\rfloor$ and make every leftover <vertex> an exceptional singleton. This is a further <refinement of a set partition>, so it cannot decrease $q$. There are at most $k2^k$ atoms, hence fewer than $k2^k\ell\leq n2^{-k}$ newly exceptional <vertices>. If $t\geq2\cdot4^k$, then $\ell\geq t/(2\cdot4^k)$, so the number of full blocks is at most $2k4^k$. Each original class produces at least one full block: its leftovers occupy less than $2^k\ell$, whereas $t\geq4^k\ell>2^k\ell$. Thus the new class count is at least $k$.
Choose $R_* =\lceil4\varepsilon^{-5}\rceil+1$, and choose an initial <integer> $k_0\geq m_0$ large enough that $R_*2^{-k_0}\leq\varepsilon/2$. Initially partition into $k_0$ equal classes and fewer than $k_0$ exceptional <vertices>. Take $n_0$ large enough that this initial exception is at most $\varepsilon n/2$. During at most $R_*$ rounds, the additional exception is at most $R_*n2^{-k_0}\leq\varepsilon n/2$, so it never exceeds $\varepsilon n\leq n/2$.
A bound on class counts is obtained by iterating $k\mapsto2k4^k$ at most $R_*$ times starting at $k_0$; call the resulting bound $M$. Increasing $n_0$ further to satisfy $n_0\geq4M4^M$ guarantees $t\geq n/(2k)\geq2\cdot4^k$ at every round, so all full-block constructions are valid. If the desired regularity had not been reached after $R_*$ refinements, the <regularity energy> increments would total more than one, impossible. Therefore the process terminates with the required partition and bounds. The singleton treatment of discarded <vertices> is what preserves <regularity energy> monotonicity during equalization.
Back to article page
