Szemerédi regularity lemma with an equitable partition and an explicit tower-type upper bound for graphs of order at least $m_0$

Each factor $\lceil {ϵ}^{-5}{2}^{m_r+5}\rceil$ is at least $1$, so $m_0\le m_1\le \cdots \le m_R=M\le n$. Choose an equitable partition ${\mathcal{P}}_0$ of $V(G)$ into exactly $m_0$ nonempty parts, whose sizes are then $\lfloor n\mathrm{/}{m}_0\rfloor$ or $\lceil n\mathrm{/}{m}_0\rceil$; this is possible because $n\ge M\ge m_0$.

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$, every piece has size $t$ or $t+1$, because $\mathrm{\mid }X\mathrm{\mid }\in \{a,a+1\}$ forces $\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 the resulting ${\mathcal{P}}^{\mathrm{\prime }}$ is an equitable refinement of $\mathcal{P}$ with exactly $kp$ parts.

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. A piece is dirty exactly when it contains a boundary between two consecutive $\mathcal{R}$-cells of the same part, and each of the at most $K-k$ such boundaries lies in one piece, so there are at most $K$ dirty pieces. Each has 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)$, using $p\le \mathrm{\mid }X\mathrm{\mid }$ and $\mathrm{\mid }X\mathrm{\mid }\le \lceil n\mathrm{/}k\rceil \le 2n\mathrm{/}k$. Hence $\mathrm{\mid }D\mathrm{\mid }\le 4Kn\mathrm{/}(kp)=2^{k+3}n\mathrm{/}p\le {ϵ}^{5}n\mathrm{/}4$.

Energy loss. 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]. Every piece outside $D$ lies in one $\mathcal{R}$-cell and is therefore itself a cell of $\mathcal{S}$, so in the sums of [L4] the two energies agree term by term on ordered pairs of such pieces. Every other ordered pair has an entry inside $D$, and those pairs carry total weight at most $2\mathrm{\mid }D\mathrm{\mid }n\mathrm{/}{n}^2=2\mathrm{\mid }D\mathrm{\mid }\mathrm{/}n$; since each squared density lies in $[0,1]$, their contribution to each of $q(\mathcal{S})$ and $q({\mathcal{P}}^{\mathrm{\prime }})$ lies in $[0,2\mathrm{\mid }D\mathrm{\mid }\mathrm{/}n]$. Hence $q({\mathcal{P}}^{\mathrm{\prime }})\ge q(\mathcal{S})-2\mathrm{\mid }D\mathrm{\mid }\mathrm{/}n\ge q(\mathcal{R})-{ϵ}^5\mathrm{/}2$.

One round. Suppose ${\mathcal{P}}_r$ is equitable, refines ${\mathcal{P}}_0$, has $k_r$ parts with $m_0\le k_r\le m_r$, and is not $ϵ$-regular. Apply [L1] to obtain a refinement ${\mathcal{R}}_r$ with at most $k_r{2}^{k_r+1}$ parts and $q({\mathcal{R}}_r)>q({\mathcal{P}}_r)+{ϵ}^5$, and let ${\mathcal{P}}_{r+1}$ be the partition step 1.2 builds from ${\mathcal{P}}_r$ and ${\mathcal{R}}_r$ with $p_r=\lceil {ϵ}^{-5}{2}^{k_r+5}\rceil$. Its hypothesis $k_r{p}_r\le n$ holds because $k_r\le m_r$ makes $k_r{p}_r\le m_{r+1}\le M\le n$. So ${\mathcal{P}}_{r+1}$ is equitable, refines ${\mathcal{P}}_r$ and hence ${\mathcal{P}}_0$, has $k_{r+1}=k_r{p}_r$ parts with $m_0\le k_r\le k_{r+1}\le m_{r+1}$, and step 3.1 gives $q({\mathcal{P}}_{r+1})>q({\mathcal{P}}_r)+{ϵ}^5\mathrm{/}2$.

If none of ${\mathcal{P}}_0,\dots ,{\mathcal{P}}_{R-1}$ were $ϵ$-regular, iterating step 4.1 would produce ${\mathcal{P}}_R$ with $q({\mathcal{P}}_R)>q({\mathcal{P}}_0)+R{ϵ}^5\mathrm{/}2\ge 2{ϵ}^{-5}\cdot {ϵ}^5\mathrm{/}2=1$, contradicting the bound $q\le 1$ of [L2].

Hence some ${\mathcal{P}}_r$ with $r<R$ is $ϵ$-regular, and step 4.1 makes it equitable with $k_r$ parts satisfying $m_0\le k_r\le m_r\le M$. That is the asserted partition.