A prescribed finite vertex partition has a bounded $ϵ$-regular refinement, equitable when the initial partition is equitable

Arbitrary refinement. Starting from ${\mathcal{P}}_0$, apply [L1] whenever the current partition is not $ϵ$-regular; each application raises the energy by more than ${ϵ}^5$ and replaces the part-count bound $k$ by $k{2}^{k+1}$. By [L2] the energy lies in $[0,1]$, so at most $\lceil {ϵ}^{-5}\rceil$ applications occur, and iterating that map $\lceil {ϵ}^{-5}\rceil$ times from $k_0$ bounds the number of parts of the resulting $ϵ$-regular refinement of ${\mathcal{P}}_0$.

Constants for the equitable case. Put $K_0=k_0$, $K_{r+1}=K_r\lceil {ϵ}^{-5}{2}^{K_r+5}\rceil$, $R=\lceil 2{ϵ}^{-5}\rceil$, and $T=K_R$. Each factor is at least $1$, so $K_0\le K_1\le \cdots \le K_R=T$.

Small graphs. Assume ${\mathcal{P}}_0$ is equitable and $n<T$. The partition of $V(G)$ into singletons refines ${\mathcal{P}}_0$, is equitable, and has $n<T$ parts. It is $ϵ$-regular: the only subset of a singleton with at least $ϵ$ times its size is the singleton itself, so every pair of singletons has density difference $0$ in [L5]; for $n=0$ the convention in [L3] gives the same conclusion.

Equitisation. Let $\mathcal{P}$ be equitable with $k$ parts, let $\mathcal{R}$ refine $\mathcal{P}$ with at most $K=k{2}^{k+1}$ parts, put $p=\lceil {ϵ}^{-5}{2}^{k+5}\rceil$, and suppose $kp\le n$. Order $V(G)$ so that each part of $\mathcal{P}$ is an interval and each cell of $\mathcal{R}$ is an interval inside its part, and cut each part $X$ into $p$ consecutive pieces of sizes $\lfloor \mathrm{\mid }X\mathrm{\mid }\mathrm{/}p\rfloor$ or $\lceil \mathrm{\mid }X\mathrm{\mid }\mathrm{/}p\rceil$. Writing $a=\lfloor n\mathrm{/}k\rfloor$ and $t=\lfloor a\mathrm{/}p\rfloor \ge 1$, the sizes $\mathrm{\mid }X\mathrm{\mid }\in \{a,a+1\}$ force $\lfloor \mathrm{\mid }X\mathrm{\mid }\mathrm{/}p\rfloor \ge t$ and $\lceil \mathrm{\mid }X\mathrm{\mid }\mathrm{/}p\rceil \le t+1$, so every piece has size $t$ or $t+1$ and the result ${\mathcal{P}}^{\mathrm{\prime }}$ is an equitable refinement of $\mathcal{P}$ with exactly $kp$ parts.

Energy loss. Call a piece dirty when it is not contained in a single cell of $\mathcal{R}$, and let $D$ be the union of the dirty pieces. Each of the at most $K-k$ boundaries between consecutive $\mathcal{R}$-cells of one part lies in exactly one piece, so at most $K$ pieces are dirty, each of size at most $\lceil \mathrm{\mid }X\mathrm{\mid }\mathrm{/}p\rceil \le 2\mathrm{\mid }X\mathrm{\mid }\mathrm{/}p\le 4n\mathrm{/}(kp)$; hence $\mathrm{\mid }D\mathrm{\mid }\le 4Kn\mathrm{/}(kp)=2^{k+3}n\mathrm{/}p\le {ϵ}^{5}n\mathrm{/}4$. Let $\mathcal{S}$ be the common refinement of ${\mathcal{P}}^{\mathrm{\prime }}$ and $\mathcal{R}$. It refines $\mathcal{R}$, so $q(\mathcal{S})\ge q(\mathcal{R})$ by [L2], while every clean piece is already a cell of $\mathcal{S}$, so by [L4] the two energies agree except on ordered pairs with an entry inside $D$, which carry total weight at most $2\mathrm{\mid }D\mathrm{\mid }\mathrm{/}n$ and squared densities in $[0,1]$. Therefore $q({\mathcal{P}}^{\mathrm{\prime }})\ge q(\mathcal{S})-2\mathrm{\mid }D\mathrm{\mid }\mathrm{/}n\ge q(\mathcal{R})-{ϵ}^5\mathrm{/}2$.

Iteration. Assume ${\mathcal{P}}_0$ is equitable with $k_0^{\mathrm{\prime }}\le K_0$ parts and $n\ge T$. Given an equitable ${\mathcal{P}}_r$ that refines ${\mathcal{P}}_0$, has $k_r\le K_r$ parts, and is not $ϵ$-regular, apply [L1] to get a refinement ${\mathcal{R}}_r$ with at most $k_r{2}^{k_r+1}$ parts and energy gain more than ${ϵ}^5$, then apply steps 2.2 and 3.1 with $p_r=\lceil {ϵ}^{-5}{2}^{k_r+5}\rceil$; the hypothesis $k_r{p}_r\le n$ holds because $k_r\le K_r$ makes $k_r{p}_r\le K_{r+1}\le T\le n$. The result ${\mathcal{P}}_{r+1}$ is equitable, refines ${\mathcal{P}}_r$ and hence ${\mathcal{P}}_0$, has $k_{r+1}=k_r{p}_r\le K_{r+1}$ parts, and satisfies $q({\mathcal{P}}_{r+1})>q({\mathcal{P}}_r)+{ϵ}^5\mathrm{/}2$.

Since energy lies in $[0,1]$ by [L2], it cannot gain ${ϵ}^5\mathrm{/}2$ at $R=\lceil 2{ϵ}^{-5}\rceil$ successive rounds, so some ${\mathcal{P}}_r$ with $r<R$ is $ϵ$-regular; it is equitable, refines ${\mathcal{P}}_0$, and has at most $K_r\le T$ parts.

Let $K$ be the larger of $T$ and the bound supplied by step 1.1; both depend only on $ϵ$ and $k_0$. Step 1.1 proves the first assertion, and steps 2.1 and 5.1 prove the equitable assertion for $n<T$ and for $n\ge T$ respectively.