Every finite graph has a linearly large $ϵ$-self-regular vertex subset

Choose an integer $s\gg {ϵ}^{-3}$ and divide $[0,1]$ into $q=\lceil 8\mathrm{/}ϵ\rceil$ intervals of length at most $ϵ\mathrm{/}8$. Repeated pigeonhole selection gives an integer $R=R(q,s)$ such that every $q$-colouring of the pairs of an $R$-set has a monochromatic $s$-set: select successively a vertex and a colour occurring on at least a $1\mathrm{/}q$ fraction of its remaining incident pairs, and take the initial set large enough for $s$ selections.

Choose $\rho >0$ much smaller than $R^{-2}{ϵ}^3$, apply [L1] at parameter $\rho$ and minimum part count much larger than $R\mathrm{/}ϵ$, and let $M$ be the resulting upper bound on the number of parts.

In the graph on the partition indices whose edges are the regular cross-pairs, fewer than $2\rho k^2$ pairs are missing by equitability. If every $R$-set contained a missing pair, double-counting pairs inside $R$-sets would force at least $\left(\genfrac{}{}{0px}{}{k}{2}\right)\mathrm{/}\left(\genfrac{}{}{0px}{}{R}{2}\right)$ missing pairs, contrary to the choice of $\rho$. Hence there is an $R$-set of indices all of whose cross-pairs are $\rho$-regular.

Colour those regular pairs by the interval containing their density. Step 1.1 supplies $s$ parts $V_1,\dots ,V_s$ whose cross-densities all lie in one interval; let $W=V_1\cup \cdots \cup V_s$. Since the partition is equitable and has at most $M$ parts, $\mathrm{\mid }W\mathrm{\mid }\ge sn\mathrm{/}(2M)$.

Let $A,B\subseteq W$ have size at least $ϵ\mathrm{\mid }W\mathrm{\mid }$, and write $A_i=A\cap V_i$, $B_j=B\cap V_j$. Pairs with $i=j$, or with $\mathrm{\mid }{A}_i\mathrm{\mid }<\rho \mathrm{\mid }{V}_i\mathrm{\mid }$ or $\mathrm{\mid }{B}_j\mathrm{\mid }<\rho \mathrm{\mid }{V}_j\mathrm{\mid }$, contribute at most $3\mathrm{/}({ϵ}^{2}s)+4\rho \mathrm{/}ϵ$ to the normalized density comparison.

On every remaining pair, regularity gives $\mathrm{\mid }d(A_i,B_j)-d(V_i,V_j)\mathrm{\mid }\le \rho$, while the density colour in step 4.1 makes any two cross-densities differ by at most $ϵ\mathrm{/}8$. Decomposing both $d(A,B)$ and $d(W,W)$ over the $s^2$ pairs and using step 5.1 therefore gives $\mathrm{\mid }d(A,B)-d(W,W)\mathrm{\mid }\le ϵ$ by the choices of $s$ and $\rho$.

For graphs large enough for [L1], steps 4.1 and 6.1 give an $ϵ$-self-regular $W$ of size at least $sn\mathrm{/}(2M)$. For the finitely many smaller orders $n\ge 1$, a singleton is $0$-self-regular and hence $ϵ$-self-regular. Shrinking $\delta$ to the minimum of $s\mathrm{/}(2M)$ and the reciprocals of those orders proves the Statement for every finite graph with at least one vertex.