Deleting a leaf and a co-leaf preserves virality of a finite forbidden family

If $\mathrm{\mid }{H}_1\mathrm{\mid }\le 2$ or $\mathrm{\mid }{H}_2\mathrm{\mid }\le 2$, the chosen graph has two vertices: a leaf or co-leaf cannot occur on fewer. Every graph on two vertices has the Erdős-Hajnal property by the at-most-three-vertex theorem, so its singleton family is viral by the single-graph equivalence. The same viral exponent works for $\mathcal{F}$: the few-copy premise for $\mathcal{F}$ includes the premise for that singleton. Hence assume both orders are at least three. Put $h=\max \{\mathrm{\mid }{H}_1\mathrm{\mid },\mathrm{\mid }{H}_2\mathrm{\mid },4\},c=4^{-h}\mathrm{.}$

Apply [L2] to $H_1$ with $\eta =c^2$, obtaining $\delta >0$; shrink $\delta$ to at most $1$ if necessary. Choose a common viral exponent $d\ge 4$ for ${\mathcal{F}}_1,{\mathcal{F}}_2$ large enough that $c^d\le \delta$. Define $a=2d^{2}h,b=a+6d+1.$ For any $0<x<c$, if every member of $\mathcal{F}$ has fewer than $(x^b\mathrm{\mid }G\mathrm{\mid }{)}^{\mathrm{\mid }H\mathrm{\mid }}$ copies in $G$, then [L2] supplies a $c^2$-restricted set of size at least $\delta \mathrm{\mid }G\mathrm{\mid }\ge c^d\mathrm{\mid }G\mathrm{\mid }$, because $x^b<c^b\le c^d\le \delta$.

We establish a one-step assertion. Let $0<x\le y\le c$, and let $Q$ be a $y^2$-restricted graph on $q$ vertices. Then at least one of these happens:

We prove that $(b,c)$ witnesses divisiveness. Fix $0<x<c$ and a nonempty graph $G$ on $n\ge x^{-b\mathrm{/}2}$ vertices satisfying the defining few-copy bounds for $\mathcal{F}$. Suppose it has no blockade required by divisiveness. Let $m\ge 2$ be the least integer with $c^{d^{m-1}}\le x$. We construct nested sets $V(G)=S_0\supseteq S_1\supseteq \cdots \supseteq S_m$ such that, for $1\le i\le m$, |S_i|\ge c^{3d^i}|S_{i-1}|, \quad G[S_i]\text{ is }c^{2d^{i-1}}\text{-restricted}.\tag{1} For $i=1$, step 1.2 gives a $c^2$-restricted set of size at least $c^{d}n\ge c^{3d}n$.

Suppose (1) is constructed through $S_i$ with $1\le i<m$, and put $y=c^{d^{i-1}}$. Minimality of $m$ gives $x<c^{d^{m-2}}\le y$; also $y\le c$. Summing the geometric exponents in (1), with $d\ge 4$, gives |S_i|\ge c^{3(d+\cdots+d^i)}n\ge c^{4d^i}n =y^{4d}n\ge x^{4d}n.\tag{2} Consequently every $H\in \mathcal{F}$ has fewer than $(x^{b-4d}\mathrm{\mid }{S}_i\mathrm{\mid }{)}^{\mathrm{\mid }H\mathrm{\mid }}$ copies in $G[S_i]$, because it has fewer than $(x^{b}n{)}^{\mathrm{\mid }H\mathrm{\mid }}$ copies in $G$. Apply step 1.3 to $Q=G[S_i]$. Its first outcome is impossible. Its blockade outcome would have length at least $y^{-1}\in [2,x^{-1}]$ and width at least $y^{a+1}\mathrm{\mid }{S}_i\mathrm{\mid }\ge y^{a+4d+1}n\ge y^{b}n$ because $b=a+6d+1$; it would be the forbidden divisive blockade. Thus its second outcome supplies $S\subseteq S_i$ of size $\mathrm{\mid }S\mathrm{\mid }\ge y^2\mathrm{\mid }{S}_i\mathrm{\mid }$ with few $H_j^{\mathrm{\prime }}$ copies for some $j\in \{1,2\}$.

Since (2) gives $\mathrm{\mid }S\mathrm{\mid }\ge y^{4d+2}n\ge y^{5d}n$, we have $y^{2d^2}\mathrm{\mid }S\mathrm{\mid }\ge y^{2d^2+5d}n\ge x^{b}n\mathrm{.}$ The final inequality uses $x\le y<1$ and $b=a+6d+1\ge 2d^2+5d$. Thus every unchanged member of ${\mathcal{F}}_j$ has fewer than $(y^{2d^2}\mathrm{\mid }S\mathrm{\mid }{)}^{\mathrm{\mid }H\mathrm{\mid }}$ copies; the replaced member $H_j^{\mathrm{\prime }}$ has the same strict bound by step 3.1. Apply virality of ${\mathcal{F}}_j$ with parameter $y^{2d}$ to obtain $S_{i+1}\subseteq S$ that is $y^{2d}=c^{2d^i}$-restricted and has $\mathrm{\mid }{S}_{i+1}\mathrm{\mid }\ge y^{2d^2}\mathrm{\mid }S\mathrm{\mid }\ge y^{2d^2+2}\mathrm{\mid }{S}_i\mathrm{\mid }\ge c^{3d^{i+1}}\mathrm{\mid }{S}_i\mathrm{\mid }\mathrm{.}$ The last inequality follows from $2d^2+2\le 3d^2$. This completes the induction.

At the final stage, $c^{d^{m-1}}\le x$, so $G[S_m]$ is $x^2$-restricted. The geometric sum in (1), together with the minimality inequality $x<c^{d^{m-2}}$, yields |S_m|\ge c^{4d^m}n\ge x^{4d^2}n\ge x^{-1},\tag{3} where the last step uses $n\ge x^{-b\mathrm{/}2}$ and $b\ge 8d^2+2$. Put $k=\lceil x^{-1\mathrm{/}2}\rceil$ and $r=\lfloor 2x\mathrm{\mid }{S}_m\mathrm{\mid }\rfloor$. As $x<c\le 1\mathrm{/}16$, one has $2\le k\le x^{-1}$, $kr\le 4x^{1\mathrm{/}2}\mathrm{\mid }{S}_m\mathrm{\mid }\le \mathrm{\mid }{S}_m\mathrm{\mid }$, and $r\ge x\mathrm{\mid }{S}_m\mathrm{\mid }\ge 1$. Choose $k$ disjoint $r$-element subsets of $S_m$. If $G[S_m]$ is sparse, they form an $x$-sparse blockade: each later vertex has at most $x^2\mathrm{\mid }{S}_m\mathrm{\mid }\le xr$ neighbors in an earlier block. If $\bar{G}[S_m]$ is sparse, they form the dense alternative. Finally $r\ge x\mathrm{\mid }{S}_m\mathrm{\mid }\ge x^{4d^2+1}n\ge n\mathrm{/}{k}^b,$ since $k\ge x^{-1\mathrm{/}2}$ and $b\ge 8d^2+2$. This contradicts step 2.1. Hence $\mathcal{F}$ is divisive, and [L4] makes it viral.