Iterative Restriction and Comb-Extraction Lemmas

Because $G$ is not $2y^4$-sparse, some vertex $v$ has degree at least $2y^4\mathrm{\mid }V(G)\mathrm{\mid }$. Let $N:=N_G(v)$. Then $\mathrm{\mid }N\mathrm{\mid }\ge 2y^4\mathrm{\mid }V(G)\mathrm{\mid }$.

Let $A^{\mathrm{\prime }}$ be the set of vertices in $V(G)\setminus (N\cup \{v\})$ with at least $\frac{1}{2}{y}^2\mathrm{\mid }N\mathrm{\mid }$ neighbours in $N$. Averaging over the edges between $A^{\mathrm{\prime }}$ and $N$, some vertex of $N$ has at least $\frac{1}{2}{y}^2\mathrm{\mid }{A}^{\mathrm{\prime }}\mathrm{\mid }$ neighbours in $A^{\mathrm{\prime }}$. Since every vertex has degree at most $y^3\mathrm{\mid }V(G)\mathrm{\mid }$ by [L1], we obtain $\frac{1}{2}{y}^2\mathrm{\mid }{A}^{\mathrm{\prime }}\mathrm{\mid }\le y^3\mathrm{\mid }V(G)\mathrm{\mid }$, so $\mathrm{\mid }{A}^{\mathrm{\prime }}\mathrm{\mid }\le 2y\mathrm{\mid }V(G)\mathrm{\mid }$.

Define $A:=V(G)\setminus (N\cup A^{\mathrm{\prime }}\cup \{v\})$. Since $G$ is $y^3$-sparse, [L1] gives $\mathrm{\mid }N\mathrm{\mid }\le y^3\mathrm{\mid }V(G)\mathrm{\mid }$, and because $\mathrm{\mid }V(G)\mathrm{\mid }\ge y^{-4}$ we have $1\le y\mathrm{\mid }V(G)\mathrm{\mid }$. Therefore $\mathrm{\mid }A\mathrm{\mid }\ge \mathrm{\mid }V(G)\mathrm{\mid }-(y^3\mathrm{\mid }V(G)\mathrm{\mid }+2y\mathrm{\mid }V(G)\mathrm{\mid }+1)\ge (1-3y)\mathrm{\mid }V(G)\mathrm{\mid }$. Also, every vertex of $A$ has fewer than $\frac{1}{2}{y}^2\mathrm{\mid }N\mathrm{\mid }$ neighbours in $N$ by definition of $A^{\mathrm{\prime }}$.

Let $N^{\mathrm{\prime }}\subseteq N$ be the set of vertices with at most $x^2\mathrm{\mid }A\mathrm{\mid }$ neighbours in $A$, and put $B:=N\setminus N^{\mathrm{\prime }}$. The number of edges between $A$ and $N^{\mathrm{\prime }}$ is at most $x^2\mathrm{\mid }A\mathrm{\mid }\mathrm{\mid }{N}^{\mathrm{\prime }}\mathrm{\mid }$, so at most $x\mathrm{\mid }A\mathrm{\mid }$ vertices of $A$ have more than $x\mathrm{\mid }{N}^{\mathrm{\prime }}\mathrm{\mid }$ neighbours in $N^{\mathrm{\prime }}$. Hence at least $\mathrm{\mid }A\mathrm{\mid }-x\mathrm{\mid }A\mathrm{\mid }\ge (1-3y-x)\mathrm{\mid }V(G)\mathrm{\mid }\ge (1-4y)\mathrm{\mid }V(G)\mathrm{\mid }$ vertices of $A$ have at most $x\mathrm{\mid }{N}^{\mathrm{\prime }}\mathrm{\mid }$ neighbours in $N^{\mathrm{\prime }}$.

If $\mathrm{\mid }{N}^{\mathrm{\prime }}\mathrm{\mid }\ge y^4\mathrm{\mid }V(G)\mathrm{\mid }$, then step 4.1 gives a set $Y\subseteq A$ with $\mathrm{\mid }Y\mathrm{\mid }\ge (1-4y)\mathrm{\mid }V(G)\mathrm{\mid }$ such that every vertex of $Y$ has at most $x\mathrm{\mid }{N}^{\mathrm{\prime }}\mathrm{\mid }$ neighbours in $N^{\mathrm{\prime }}$. By [L2], the pair $(X,Y):=(N^{\mathrm{\prime }},Y)$ is then a forbidden large sparse pair, contradicting the hypothesis. Therefore $\mathrm{\mid }{N}^{\mathrm{\prime }}\mathrm{\mid }<y^4\mathrm{\mid }V(G)\mathrm{\mid }$.

Since $\mathrm{\mid }N\mathrm{\mid }\ge 2y^4\mathrm{\mid }V(G)\mathrm{\mid }$ by step 1.1 and $\mathrm{\mid }{N}^{\mathrm{\prime }}\mathrm{\mid }<y^4\mathrm{\mid }V(G)\mathrm{\mid }$ by step 5.1, we have $\mathrm{\mid }B\mathrm{\mid }=\mathrm{\mid }N\mathrm{\mid }-\mathrm{\mid }{N}^{\mathrm{\prime }}\mathrm{\mid }\ge y^4\mathrm{\mid }V(G)\mathrm{\mid }$. By definition of $B$, every vertex of $B$ has more than $x^2\mathrm{\mid }A\mathrm{\mid }$ neighbours in $A$. Also step 3.1 gives at most $\frac{1}{2}{y}^2\mathrm{\mid }N\mathrm{\mid }$ neighbours in $N$ for each vertex of $A$, while step 5.1 implies $\mathrm{\mid }B\mathrm{\mid }>\mathrm{\mid }N\mathrm{\mid }\mathrm{/}2$; hence $\frac{1}{2}{y}^2\mathrm{\mid }N\mathrm{\mid }<y^2\mathrm{\mid }B\mathrm{\mid }$, so every vertex of $A$ has at most $y^2\mathrm{\mid }B\mathrm{\mid }$ neighbours in $B$. Therefore $A$ is $y^2$-sparse to $B$.

Step 3.1 gives $A\subseteq V(G)\setminus N_G[v]$, step 1.1 gives $B\subseteq N_G(v)$, and steps 3.1 and 6.1 give the size, sparsity, and neighbourhood clauses. These are exactly the four clauses of the statement.

By [L1], fix $H$ and $v$ so that the modified family ${\mathcal{F}}^{\mathrm{\prime }}:=\{H\setminus \{v\}\}\cup (\mathcal{F}\setminus \{H\})$ has the Erdős-Hajnal property. By the implication from assertion 1 to assertion 3 in [L2], the family ${\mathcal{F}}^{\mathrm{\prime }}$ is viral.

Apply [L3] with both leaf-deletion slots equal to the same graph $H$ and with the same leaf $v$. The two modified families are both ${\mathcal{F}}^{\mathrm{\prime }}$, so step 1.1 makes them viral. Therefore $\mathcal{F}$ itself is viral. Using the implication from assertion 3 to assertion 2 in [L2], choose $d>0$ such that every $\mathcal{F}$-free graph has an $ϵ$-restricted induced subgraph on at least ${ϵ}^d$ times its number of vertices for every $ϵ\in (0,\frac{1}{2})$. Set $h:=1$.

Since $G$ is $\mathcal{F}$-free by [L4], step 2.1 applies to $G$ with $ϵ:=y^b\in (0,\frac{1}{2})$. We obtain a $y^b$-restricted induced subgraph of $G$ with at least $(y^b{)}^d\mathrm{\mid }V(G)\mathrm{\mid }=y^{bd}\mathrm{\mid }V(G)\mathrm{\mid }$ vertices. Since $y\in (0,\frac{1}{2})$, one has $y^{bd}\ge y^{bd+1}$, so this induced subgraph also has at least $y^{bd+1}\mathrm{\mid }V(G)\mathrm{\mid }$ vertices. Hence outcome 2 holds.

Because outcome 2 always holds, the displayed dichotomy is satisfied.

Hypothesis 1 supplies a nonempty $c$-sparse vertex set, because $c$-sparse sets are nonempty by [L1]. Hence $\mathrm{\mid }V(G)\mathrm{\mid }>0$.

For each nonempty induced subgraph $E$ of $G$, let $\mu (E)$ be its maximum degree divided by $\mathrm{\mid }V(E)\mathrm{\mid }$; by [L1], the graph $E$ is $\lambda$-sparse exactly when $\mu (E)\le \lambda$. Define $\lambda (E):=\max (x^{b_1},\mu (E))$. Hypothesis 1 gives a $c$-sparse induced subgraph $E_0$ with at least $c^{b_2}\mathrm{\mid }V(G)\mathrm{\mid }$ vertices, so $\lambda (E_0)\le c$ and $\mathrm{\mid }V(E_0)\mathrm{\mid }\ge \lambda (E_0{)}^{b_2}\mathrm{\mid }V(G)\mathrm{\mid }$. Because $G$ has only finitely many induced subgraphs, the set of values $\lambda (E)$ with $\lambda (E)\le c$ and $\mathrm{\mid }V(E)\mathrm{\mid }\ge \lambda (E{)}^{b_2}\mathrm{\mid }V(G)\mathrm{\mid }$ has a minimum. Choose an induced subgraph $F$ for which that minimum is attained, and write $\lambda :=\lambda (F)$.

Suppose that $\lambda \ge x$. Then hypothesis 2 applies to $F$ and produces a ${\lambda }^{b_1}$-sparse induced subgraph $F^{\mathrm{\prime }}\subseteq F$ with at least ${\lambda }^{b_3}\mathrm{\mid }V(F)\mathrm{\mid }\ge {\lambda }^{b_2+b_3}\mathrm{\mid }V(G)\mathrm{\mid }\ge {\lambda }^{b_1{b}_2}\mathrm{\mid }V(G)\mathrm{\mid }$ vertices, where the last inequality uses $b_1{b}_2\ge b_2+b_3$. Since $F^{\mathrm{\prime }}$ is ${\lambda }^{b_1}$-sparse, we have $\mu (F^{\mathrm{\prime }})\le {\lambda }^{b_1}$ and therefore $\lambda (F^{\mathrm{\prime }})=\max (x^{b_1},\mu (F^{\mathrm{\prime }}))\le {\lambda }^{b_1}<\lambda$. Also $\mathrm{\mid }V(F^{\mathrm{\prime }})\mathrm{\mid }\ge \lambda (F^{\mathrm{\prime }}{)}^{b_2}\mathrm{\mid }V(G)\mathrm{\mid }$. This contradicts the minimal choice of $\lambda$. Therefore $\lambda <x$.

Since $\lambda =\lambda (F)$, step 1.2 gives $x^{b_1}\le \lambda$, and step 2.1 gives $\lambda <x$. Because $F$ is $\lambda$-sparse, it is also $x$-sparse. Moreover $\mathrm{\mid }V(F)\mathrm{\mid }\ge {\lambda }^{b_2}\mathrm{\mid }V(G)\mathrm{\mid }\ge (x^{b_1}{)}^{b_2}\mathrm{\mid }V(G)\mathrm{\mid }=x^{b_1{b}_2}\mathrm{\mid }V(G)\mathrm{\mid }$.

The induced subgraph $F$ from step 3.1 is the required $x$-sparse induced subgraph.

[assume-case pair] If outcome 1 already holds, there is nothing to prove.

[assume-case sparser] If outcome 2 already holds, there is nothing to prove.

[assume-case comb] Assume now that outcomes 1 and 2 both fail. Then [L1] gives a vertex $v\in V(G)$ and disjoint sets $A,B\subseteq V(G)\setminus \{v\}$ with $A\subseteq V(G)\setminus N_G[v]$, $B\subseteq N_G(v)$, and the displayed nearly covered sparse pair properties. In particular $A$ and $B$ are nonempty.

Apply [L2] with $\xi =x^2$ to the sets $A,B$. We obtain a set $S\subseteq A$ with $\mathrm{\mid }S\mathrm{\mid }\le \lceil x^{-2}\rceil$ such that at least half of the vertices of $B$ have a neighbour in $S$. Let $B^{\mathrm{\prime }}\subseteq B$ be the set of vertices with a neighbour in $S$; then $\mathrm{\mid }{B}^{\mathrm{\prime }}\mathrm{\mid }\ge \mathrm{\mid }B\mathrm{\mid }\mathrm{/}2\ge \frac{1}{2}{y}^4\mathrm{\mid }V(G)\mathrm{\mid }$.

Consider the bipartite graph between $S$ and $B^{\mathrm{\prime }}$. Every vertex of $B^{\mathrm{\prime }}$ has a neighbour in $S$ by definition. Since $A$ is $y^2$-sparse to $B$ and $S\subseteq A$, every vertex of $S$ has at most $y^2\mathrm{\mid }B\mathrm{\mid }$ neighbours in $B^{\mathrm{\prime }}$. Apply [L3] with $d:=1\mathrm{/}2$, $\mathrm{\Delta }:=y^2\mathrm{\mid }B\mathrm{\mid }$, and $\mathrm{\Gamma }:=\mathrm{\mid }B\mathrm{\mid }$.

The second alternative of [L3] is impossible for these parameters, because it would give $\mathrm{\mid }{B}^{\mathrm{\prime }}\mathrm{\mid }\le \frac{3^{3\mathrm{/}2}}{3\mathrm{/}2-\sqrt{3\mathrm{/}2}}\mathrm{\mid }B{\mathrm{\mid }}^{1\mathrm{/}2}(y^2\mathrm{\mid }B\mathrm{\mid }{)}^{1\mathrm{/}2}=\frac{3^{3\mathrm{/}2}}{3\mathrm{/}2-\sqrt{3\mathrm{/}2}}y\mathrm{\mid }B\mathrm{\mid }$. The constant in front of $y\mathrm{\mid }B\mathrm{\mid }$ is less than $20$, while $\mathrm{\mid }{B}^{\mathrm{\prime }}\mathrm{\mid }\ge \mathrm{\mid }B\mathrm{\mid }\mathrm{/}2>20y\mathrm{\mid }B\mathrm{\mid }$ since $y\le 2^{-8}<1\mathrm{/}40$. Hence [L3] yields a $(\mathrm{\ell },\mathrm{\mid }B\mathrm{\mid }\mathrm{/}{\mathrm{\ell }}^2)$-comb $((a_i,B_i):i\in [\mathrm{\ell }])$ with each $a_i\in S$ and each $B_i\subseteq B^{\mathrm{\prime }}$.

Because the teeth $a_i$ are distinct members of $S$, we have $\mathrm{\ell }\le \mathrm{\mid }S\mathrm{\mid }\le \lceil x^{-2}\rceil$. Also [L4] gives $\mathrm{\mid }{B}_i\mathrm{\mid }\ge \mathrm{\mid }B\mathrm{\mid }\mathrm{/}{\mathrm{\ell }}^2$ for each tooth block, while every $a_i\in S\subseteq A$ has at most $y^2\mathrm{\mid }B\mathrm{\mid }$ neighbours in $B$. Since $a_i$ is complete to $B_i$ by [L4], this forces $\mathrm{\mid }B\mathrm{\mid }\mathrm{/}{\mathrm{\ell }}^2\le \mathrm{\mid }{B}_i\mathrm{\mid }\le y^2\mathrm{\mid }B\mathrm{\mid }$, and therefore $\mathrm{\ell }\ge y^{-1}$. Finally $\mathrm{\mid }B\mathrm{\mid }\ge y^4\mathrm{\mid }V(G)\mathrm{\mid }$ from step 1.3, so each block has size at least $y^4\mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}{\mathrm{\ell }}^2$.

By step 1.3, we already have a vertex $v$ with $B\subseteq N_G(v)$ and $A\subseteq V(G)\setminus N_G[v]$. Since each $a_i\in A$ and each $B_i\subseteq B$, the vertex $v$ is complete to ${\bigcup }_i{B}_i$ and anticomplete to $\{a_i:i\in [\mathrm{\ell }]\}$. Together with step 5.1, this is exactly outcome 3.

The three cases 1.1, 1.2, and 1.3 exhaust the possibilities, so one of the stated outcomes always holds.