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.

Fix $H,v$ from [L1], put $r=\mathrm{\mid }H\mathrm{\mid }$, and choose a viral exponent $D\ge 1$ for ${\mathcal{F}}^{\mathrm{\prime }}$ by [L2]. If $r=2$, then $H$ is an edge, so the $H$-free graph $G$ is stable and its whole vertex set is $0$-sparse. Taking $d=h=1$ gives outcome 2 for all $y,b$. Hence assume $r\ge 3$ and set $d=D(r-1)+2$ and $h=2r$. These constants depend only on $\mathcal{F}$.

If $y\ge (2r{)}^{-1}$, then $(1-hy)n\le 0$. Taking $X=V(G)$ and $Y=\mathrm{\varnothing }$ gives outcome 1, since $y^{bd+1}\le 1$. Hence assume $y<(2r{)}^{-1}$. Put $x=\min \{y\mathrm{/}2,(2n{)}^{-1}\}>0$ and $a=bD(r-1)+3$. Then $x\le y$, $a\ge 2$, and [L3] applies. Its many-$H$ outcome is impossible because $G$ is $\mathcal{F}$-free.

Suppose the few-$H-v$ outcome of [L3] holds. It gives $S\subseteq V(G)$ with $\mathrm{\mid }S\mathrm{\mid }\ge yn$ and ${\mathrm{ind}}_{H-v}(G[S])\le y^{a-2}\mathrm{\mid }S{\mathrm{\mid }}^{r-1}<y^{bD(r-1)}\mathrm{\mid }S{\mathrm{\mid }}^{r-1}$, since $a-2=bD(r-1)+1$ and $y<1$. Every unchanged member of ${\mathcal{F}}^{\mathrm{\prime }}$ belongs to $\mathcal{F}$, so it has zero copies in $G[S]$. The viral premise for ${\mathcal{F}}^{\mathrm{\prime }}$ therefore holds at $ϵ=y^b$. Virality yields a $y^b$-restricted induced subgraph with at least $y^{bD}\mathrm{\mid }S\mathrm{\mid }\ge y^{bD+1}n\ge y^{bd+1}n$ vertices. This is outcome 2.

Otherwise [L3] gives disjoint $A,B$ with $\mathrm{\mid }A\mathrm{\mid }\ge y^{a}n$, $\mathrm{\mid }B\mathrm{\mid }\ge (1-ry)n\ge (1-hy)n$, and $B$ $x$-sparse to $A$. Since $x\mathrm{\mid }A\mathrm{\mid }\le xn\le 1\mathrm{/}2$, every vertex of $B$ has integer degree zero into $A$, so $B$ is anticomplete to $A$. Also $bd+1=bD(r-1)+2b+1\ge a$ because $b>1$. Thus $\mathrm{\mid }A\mathrm{\mid }\ge y^{bd+1}n$, and $X=A,Y=B$ give outcome 1.

Step 2.1 handles the large-$y$ case, while steps 3.1 and 3.2 exhaust the two remaining alternatives of [L3]. Thus one of the stated outcomes always holds.

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.