Equitable strong regularity lemma: a very regular refinement that changes energy only slightly

If $ϵ\le {ϵ}^{\mathrm{\prime }}$ then every $ϵ$-regular pair is ${ϵ}^{\mathrm{\prime }}$-regular, because the subsets tested at parameter ${ϵ}^{\mathrm{\prime }}$ are among those tested at $ϵ$; by [L4] the same monotonicity passes to partitions. So replacing each ${ϵ}_i$ by $\min ({ϵ}_i,1\mathrm{/}2)$ keeps the sequence positive and nonincreasing and only strengthens every conclusion, and we may assume ${ϵ}_i<1$ for all $i$. Let $M_0=M_0({ϵ}_0,m_0)$ be the constant of [L2].

Small graphs. Suppose $m_0\le n<M_0$ and let $\mathcal{P}=\mathcal{Q}$ be the partition of $V(G)$ into singletons. It refines itself, is equitable, and has $n\ge m_0$ parts. The only subset of a singleton of size at least $ϵ$ times its size is the singleton itself, so by [L5] every pair of singletons is $ϵ$-regular for every $ϵ>0$, giving conclusions 2 and 3; and $q(\mathcal{Q})=q(\mathcal{P})$ gives conclusion 4.

Large graphs. Suppose $n\ge M_0$. Use [L2] to choose an equitable ${ϵ}_0$-regular partition ${\mathcal{P}}_0$ with $m_0\le \mathrm{\mid }{\mathcal{P}}_0\mathrm{\mid }\le M_0$. Having constructed ${\mathcal{P}}_i$, apply [L1] to ${\mathcal{P}}_i$ with parameter ${ϵ}_{\mathrm{\mid }{\mathcal{P}}_i\mathrm{\mid }}$ to choose an equitable refinement ${\mathcal{P}}_{i+1}$ that is ${ϵ}_{\mathrm{\mid }{\mathcal{P}}_i\mathrm{\mid }}$-regular.

Each part count is bounded by a function of the preceding one and the fixed sequence, so for every fixed number of stages all $\mathrm{\mid }{\mathcal{P}}_i\mathrm{\mid }$ are bounded independently of $G$. A refinement has at least as many parts as the partition it refines, so $\mathrm{\mid }{\mathcal{P}}_i\mathrm{\mid }\ge \mathrm{\mid }{\mathcal{P}}_0\mathrm{\mid }\ge m_0$ for every $i$.

Set $R=\lceil 1\mathrm{/}{ϵ}_0\rceil +1$. If $q({\mathcal{P}}_{i+1})>q({\mathcal{P}}_i)+{ϵ}_0$ for every $i<R$, telescoping would give $q({\mathcal{P}}_R)>1$, contrary to [L3]. Hence some $i<R$ satisfies $q({\mathcal{P}}_{i+1})\le q({\mathcal{P}}_i)+{ϵ}_0$; put $\mathcal{P}={\mathcal{P}}_i$ and $\mathcal{Q}={\mathcal{P}}_{i+1}$.

Step 2.2 supplies refinement, equitability, and ${ϵ}_{\mathrm{\mid }\mathcal{P}\mathrm{\mid }}$-regularity of $\mathcal{Q}$. Also $\mathcal{P}$ is ${ϵ}_0$-regular: this holds for ${\mathcal{P}}_0$ by construction, and every later ${\mathcal{P}}_i$ is ${ϵ}_{\mathrm{\mid }{\mathcal{P}}_{i-1}\mathrm{\mid }}$-regular with ${ϵ}_{\mathrm{\mid }{\mathcal{P}}_{i-1}\mathrm{\mid }}\le {ϵ}_0$, which gives ${ϵ}_0$-regularity by step 1.1. Step 3.1 gives $\mathrm{\mid }\mathcal{P}\mathrm{\mid }\ge m_0$ and step 3.2 the energy bound.

Let $M$ be the largest of $M_0$ and the recursively obtained part-count bounds through stage $R$. Step 2.1 settles $n<M_0$ and steps 3.1 and 4.1 settle $n\ge M_0$, so in both cases $\mathrm{\mid }\mathcal{Q}\mathrm{\mid }\le M$ and all five conclusions hold.