Every $H$-free graph partitions into boundedly many vertex sets of self-density at most $ϵ$ or at least $1-ϵ$

Let ${\delta }_0>0$ be the constant from [L1], set $\rho :=\min \{{\delta }_0,\frac{1}{2}\}$, and note that $0<\rho \le \frac{1}{2}$. Then every nonempty $H$-free graph $J$ contains a set $X\subseteq V(J)$ with $\mathrm{\mid }X\mathrm{\mid }\ge \rho \mathrm{\mid }V(J)\mathrm{\mid }$ and either $d_J(X,X)\le ϵ\mathrm{/}2$ or $d_J(X,X)\ge 1-ϵ\mathrm{/}2$.

Since $0<1-\rho <1$, [L3] applied to $r=1-\rho$ yields a natural number $t\ge 1$ with $(1-\rho {)}^t<\rho ϵ\mathrm{/}16$.

Let $G$ be an $H$-free finite simple graph. If $V(G)=\mathrm{\varnothing }$, the empty partition works, so assume $n:=\mathrm{\mid }V(G)\mathrm{\mid }>0$. Put $R_0:=V(G)$. For each $i=1,\dots ,t$, if $R_{i-1}=\mathrm{\varnothing }$ stop; otherwise the induced subgraph $G[R_{i-1}]$ is $H$-free by [L2], so step 1.1 and [F1] give a nonempty set $X_i\subseteq R_{i-1}$ with $\mathrm{\mid }{X}_i\mathrm{\mid }\ge \rho \mathrm{\mid }{R}_{i-1}\mathrm{\mid }$ and either $d_G(X_i,X_i)\le ϵ\mathrm{/}2$ or $d_G(X_i,X_i)\ge 1-ϵ\mathrm{/}2$. Define $R_i:=R_{i-1}\setminus X_i$.

If the process stops at some stage $i\le t$ because $R_{i-1}=\mathrm{\varnothing }$, then the nonempty extracted sets $X_1,\dots ,X_{i-1}$ partition $V(G)$ and each already has self-density at most $ϵ\mathrm{/}2$ or at least $1-ϵ\mathrm{/}2$, hence in particular at most $ϵ$ or at least $1-ϵ$.

Assume now that the process does not stop before stage $t$. Then $X_1,\dots ,X_t$ are pairwise disjoint nonempty sets, and an induction on $i$ using step 2.2 gives $\mathrm{\mid }{R}_i\mathrm{\mid }\le (1-\rho )\mathrm{\mid }{R}_{i-1}\mathrm{\mid }$ for every $i\le t$. Hence $\mathrm{\mid }{R}_t\mathrm{\mid }\le (1-\rho {)}^{t}n<(\rho ϵ\mathrm{/}16)n$ by step 2.1, while $\mathrm{\mid }{X}_1\mathrm{\mid }\ge \rho n$ by step 2.2.

Put $Y_1:=X_1\cup R_t$ and $Y_i:=X_i$ for $2\le i\le t$. Then $Y_1,\dots ,Y_t$ partition $V(G)$. Writing $x:=\mathrm{\mid }{X}_1\mathrm{\mid }$, $r:=\mathrm{\mid }{R}_t\mathrm{\mid }$, $y:=\mathrm{\mid }{Y}_1\mathrm{\mid }=x+r$ and $\alpha :=r\mathrm{/}x$, step 3.2 gives $\alpha <ϵ\mathrm{/}16$.

If $d_G(X_1,X_1)\le ϵ\mathrm{/}2$, then $e_G(Y_1,Y_1)\le e_G(X_1,X_1)+2ry$ because the new ordered edges are those incident with at least one vertex of $R_t$. Therefore $d_G(Y_1,Y_1)\le (ϵ\mathrm{/}2)(x\mathrm{/}y{)}^2+2r\mathrm{/}y\le ϵ\mathrm{/}2+2\alpha <ϵ$.

If instead $d_G(X_1,X_1)\ge 1-ϵ\mathrm{/}2$, then $d_G(Y_1,Y_1)\ge d_G(X_1,X_1)(x\mathrm{/}y{)}^2\ge (1-ϵ\mathrm{/}2)\mathrm{/}(1+\alpha {)}^2$. Since $\alpha <ϵ\mathrm{/}16$ and $ϵ<1\mathrm{/}2$, one has $(1+\alpha {)}^2<(1+ϵ\mathrm{/}16{)}^2\le 1+ϵ\mathrm{/}2$, so $d_G(Y_1,Y_1)>(1-ϵ\mathrm{/}2)\mathrm{/}(1+ϵ\mathrm{/}2)>1-ϵ$.

In the situation of steps 3.2 and 4.1, step 5.1 or 5.2 handles $Y_1$, while each $Y_i=X_i$ for $i\ge 2$ already has self-density at most $ϵ\mathrm{/}2$ or at least $1-ϵ\mathrm{/}2$. Therefore every part of the partition has self-density at most $ϵ$ or at least $1-ϵ$.

Step 3.1 settles the case where the extraction stops early, and step 6.1 settles the case where it reaches stage $t$. So $B:=t$ works for every $H$ and $ϵ$.