Property (*) and leaf reducibility imply generalized niceness

Let $c_1^{\mathrm{\prime }}>0$, $c_4^{\mathrm{\prime }}\ge 4$, and $d\ge 58c_4^{\mathrm{\prime }}$ be the constants from [L1]. Set $c_1:=10d^2,c_2:=d,c_3:=156c_4^{\mathrm{\prime }}d,c_4:=c_1^{\mathrm{\prime }},c_5:=2d,c_6:=5d,c_7:=5d,c_8:=116c_4^{\mathrm{\prime }}d\mathrm{.}$ Then $c_1\ge 3$, $c_2\ge 8$, $c_6\ge 1$, and $c_7\ge 4$.

Let $G$ be an $\bar{\mathcal{F}}$-free graph and let $ϵ\in (0,\frac{1}{2})$. If outcome 2, 3, or 4 of [L4] already holds for these constants, there is nothing left to prove. So assume for contradiction that all three fail, and write $x:={ϵ}^{5d}$.

If $\mathrm{\mid }G\mathrm{\mid }<{ϵ}^{-1}$, then ${ϵ}^{c_3}\mathrm{\mid }G\mathrm{\mid }\le {ϵ}^{c_3-1}\le 1,$ because $c_3>1$. Any vertex of $G$ therefore gives a clique or stable set of size at least $({ϵ}^{c_3}\mathrm{\mid }G\mathrm{\mid }{)}^{c_4}$, so outcome 2 of [L4] holds. Hence we may assume that $\mathrm{\mid }G\mathrm{\mid }\ge {ϵ}^{-1}$.

If $\mathrm{\mid }G\mathrm{\mid }\le {ϵ}^{-10d^2}$, then choose $\lceil {ϵ}^{-1}\rceil$ distinct vertices of $G$ and make them singleton blocks. Step 3.1 makes this possible, and each singleton has size $1\ge {ϵ}^{10d^2}\mathrm{\mid }G\mathrm{\mid }={ϵ}^{c_1}\mathrm{\mid }G\mathrm{\mid }\mathrm{.}$ Every pair of singleton blocks is either complete or anticomplete, hence either complete or weakly ${ϵ}^d$-sparse. Thus outcome 1 of [L4] holds. Therefore we may assume that $\mathrm{\mid }G\mathrm{\mid }\ge {ϵ}^{-10d^2}$.

Under steps 2.1 and 4.1, [L2] applies to every induced subgraph $F$ of $G$ with $\mathrm{\mid }F\mathrm{\mid }\ge {ϵ}^d\mathrm{\mid }G\mathrm{\mid }$.

If an induced subgraph $F$ of $G$ with $\mathrm{\mid }F\mathrm{\mid }\ge {ϵ}^d\mathrm{\mid }G\mathrm{\mid }$ contained a clique or stable set of size at least $(x^{31c_4^{\mathrm{\prime }}}\mathrm{\mid }F\mathrm{\mid }{)}^{c_1^{\mathrm{\prime }}}$, then $x^{31c_4^{\mathrm{\prime }}}\mathrm{\mid }F\mathrm{\mid }\ge x^{31c_4^{\mathrm{\prime }}}{ϵ}^d\mathrm{\mid }G\mathrm{\mid }={ϵ}^{155c_4^{\mathrm{\prime }}d+d}\mathrm{\mid }G\mathrm{\mid }\ge {ϵ}^{156c_4^{\mathrm{\prime }}d}\mathrm{\mid }G\mathrm{\mid }={ϵ}^{c_3}\mathrm{\mid }G\mathrm{\mid },$ so outcome 2 would hold, contrary to step 2.1. Likewise, if such an $F$ contained a complete or anticomplete $(k,\mathrm{\mid }F\mathrm{\mid }\mathrm{/}{k}^d)$-blockade with $k\ge x^{-1}$, then $\frac{\mathrm{\mid }F\mathrm{\mid }}{k^d}\ge \frac{{ϵ}^d\mathrm{\mid }G\mathrm{\mid }}{k^d}\ge \frac{\mathrm{\mid }G\mathrm{\mid }}{k^{2d}},$ so outcome 3 would hold, again contrary to step 2.1. Therefore [L2] really does give the pure-or-$x$-sparse blockade alternative on every such $F$.

By steps 4.1 and 6.1, the hypotheses of [L3] are satisfied with the parameter $d$ and $x={ϵ}^{5d}$: the graph $G$ has order at least ${ϵ}^{-10d^2}$, and every induced subgraph $F$ with $\mathrm{\mid }F\mathrm{\mid }\ge {ϵ}^d\mathrm{\mid }G\mathrm{\mid }$ has a pure or $x$-sparse $(k,\mathrm{\mid }F\mathrm{\mid }\mathrm{/}{k}^d)$-blockade for some integer $k\in [2,x^{-1}]$. Hence $G$ has an $({ϵ}^{-1},{ϵ}^{10d^2}\mathrm{\mid }G\mathrm{\mid })$-blockade whose distinct block pairs are either complete or weakly ${ϵ}^d$-sparse. This is exactly outcome 1 of [L4], because $c_1=10d^2$ and $c_2=d$.

Outcome 1 follows whenever outcomes 2, 3, and 4 fail, and step 1.1 records the remaining lower-bound requirements on the constants. Therefore the constants from step 1.1 satisfy Definition [L4], so $\mathcal{F}$ is generalized nice.