Every finite family with the Erdős–Hajnal property is viral

If $K_0\in \mathcal{F}$, then every nonempty graph $G$ has ${\mathrm{ind}}_{K_0}(G)=1$, so the inequality ${\mathrm{ind}}_{K_0}(G)<({ϵ}^d\mathrm{\mid }V(G)\mathrm{\mid }{)}^0$ reads $1<1$ and has no nonempty instance; if $K_1\in \mathcal{F}$, then ${\mathrm{ind}}_{K_1}(G)=\mathrm{\mid }V(G)\mathrm{\mid }$ and the inequality ${\mathrm{ind}}_{K_1}(G)<{ϵ}^d\mathrm{\mid }V(G)\mathrm{\mid }$ is impossible because ${ϵ}^d<1$. Thus in either case $\mathcal{F}$ is viral vacuously. We may therefore assume from now on that every $H\in \mathcal{F}$ has at least two vertices.

Choose an Erdős–Hajnal constant $c>0$ for the class of $\mathcal{F}$-free graphs.

Apply [L12] to $1\mathrm{/}c$ to choose a natural number $m\ge 1$ with $1\mathrm{/}c<m$, so $1\mathrm{/}m<c$; by [L1], the exponent $1\mathrm{/}m$ is also an Erdős–Hajnal constant for the class of $\mathcal{F}$-free graphs.

Write $q:=\mathrm{\mid }\mathcal{F}\mathrm{\mid }$. Since [L11] makes $(7x{)}^{2m}\mathrm{/}{2}^x\to 0$ and $q(7x{)}^m\mathrm{/}{2}^{2x}\to 0$ as $x\to +\mathrm{\infty }$, choose an integer $d>4m$ such that $32(7d{)}^{2m}<2^{d-4m}$ and $8q(7d{)}^m<2^{2d-2m}$.

Let $ϵ\in (0,\frac{1}{2})$ and let $G$ be a nonempty graph on $n$ vertices with ${\mathrm{ind}}_H(G)<({ϵ}^{d}n{)}^{\mathrm{\mid }V(H)\mathrm{\mid }}$ for every $H\in \mathcal{F}$. Put $\delta :={ϵ}^d$, $\mathrm{\ell }:=\lceil d\log (1\mathrm{/}ϵ)\mathrm{/}ϵ\rceil$, $k:=2\mathrm{\ell }$, and $t:=k^m$. If $\delta n<1$, then any singleton vertex set is $0$-sparse and hence $ϵ$-restricted, with size $1>\delta n$; so we may assume $\delta n\ge 1$.

Applying [L9] to $x=1\mathrm{/}ϵ-1>0$ gives $1\mathrm{/}ϵ\le \exp (1\mathrm{/}ϵ-1)$, and [L10] therefore yields $\log (1\mathrm{/}ϵ)<1\mathrm{/}ϵ$. Hence $\mathrm{\ell }\le d\mathrm{/}{ϵ}^2+1$, so $k=2\mathrm{\ell }\le 2d\mathrm{/}{ϵ}^2+2\le 7d\mathrm{/}{ϵ}^2$, and therefore $t\le (7d{)}^m{ϵ}^{-2m}$.

From [L9] we have $1-ϵ\le \exp (-ϵ)$, so $(1-ϵ{)}^{\mathrm{\ell }}\le \exp (-ϵ\mathrm{\ell })$. Since $\mathrm{\ell }\ge d\log (1\mathrm{/}ϵ)\mathrm{/}ϵ$, strict increase of the exponential and [L10] give $\exp (-ϵ\mathrm{\ell })\le \exp (-d\log (1\mathrm{/}ϵ))={ϵ}^d=\delta$. Thus $(1-ϵ{)}^{\mathrm{\ell }}n\le \delta n$.

Suppose there were no $ϵ$-restricted subset of $V(G)$ of size at least $\delta n$, and put $u:=\lceil \delta n\rceil$. Because vertex-set sizes are integers, this means there is no $ϵ$-restricted subset of size at least $u$. Since step 5.2 gives $(1-ϵ{)}^{\mathrm{\ell }}n\le \delta n\le u$, no induced subgraph of $G$ on at least $u$ vertices is $ϵ$-sparse or $ϵ$-dense. By [L7] and [L8], every induced subgraph of $G$ and of $\bar{G}$ on at least $u$ vertices therefore has maximum degree at least $ϵ\mathrm{\mid }S\mathrm{\mid }-1$.

Step 5.1 gives $t{\delta }^2\le (7d{)}^m{ϵ}^{2d-2m}\le (7d{)}^m{2}^{-(2d-2m)}$ and $t^2\delta \le (7d{)}^{2m}{ϵ}^{d-4m}\le (7d{)}^{2m}{2}^{-(d-4m)}$, so step 3.1 yields $8qt{\delta }^2\le 1$ and $32t^2\delta \le 1$. Since $\delta n\ge 1$, the second inequality forces $n\ge 1\mathrm{/}\delta \ge 32t^2>2t$.

Every $\mathcal{F}$-free graph on exactly $t=k^m$ vertices satisfies $\mathrm{hom}(H)\ge t^{1\mathrm{/}m}=(k^m{)}^{1\mathrm{/}m}=k$ by steps 2.1 and [L2]. Hence the class of $\mathcal{F}$-free graphs has the $(t,k)$-homogeneous property.

Step 6.1 gives the hypotheses of [L6] for both $G$ and $\bar{G}$, so each has at most $\left(\genfrac{}{}{0px}{}{n}{\mathrm{\ell }}\right)\left(\genfrac{}{}{0px}{}{u}{k-\mathrm{\ell }}\right)$ stable $k$-sets. By [L7], the stable $k$-sets of $\bar{G}$ are exactly the cliques of $G$. Since $k=2\mathrm{\ell }$, $u=\lceil \delta n\rceil$, and step 4.1 gives $\delta n\ge 1$, one has $u\le \delta n+1\le 2\delta n$. Hence $G$ has at most

Choose $X$ uniformly from $[V(G){]}^{2t}$. Fix $H\in \mathcal{F}$ and put $h:=\mathrm{\mid }V(H)\mathrm{\mid }$. If $h>2t$, then no $2t$-element vertex set can contain the $h$-vertex image of an induced embedding of $H$, so ${\mathrm{ind}}_H(G[X])=0$ for every $X$. Suppose instead that $h\le 2t$. Then step 6.2 gives $h\le 2t<n$, so an induced embedding of $H$ into $G$ survives in $G[X]$ exactly when $X$ contains its $h$-vertex image, which happens with probability $\frac{\left(\genfrac{}{}{0px}{}{n-h}{2t-h}\right)}{\left(\genfrac{}{}{0px}{}{n}{2t}\right)}={\prod }_{j=0}^{h-1}\frac{2t-j}{n-j}\le {\left(\frac{2t}{n}\right)}^h\mathrm{.}$ If $p_H$ denotes that survival probability, then $\mathbb{E}[{\mathrm{ind}}_H(G[X])]={\mathrm{ind}}_H(G)p_H<(\delta n{)}^h(2t\mathrm{/}n{)}^h=(2t\delta {)}^h$. So the same upper bound holds in both cases.

Let $Y(X):={\sum }_{H\in \mathcal{F}}{\mathrm{ind}}_H(G[X])$. Step 1.1 gives $\mathrm{\mid }V(H)\mathrm{\mid }\ge 2$ for every $H\in \mathcal{F}$, and step 6.2 gives $2t\delta \le 1\mathrm{/}(16t)\le 1$. Hence step 7.2 implies $\mathbb{E}[{\mathrm{ind}}_H(G[X])]<(2t\delta {)}^2$ for every $H\in \mathcal{F}$. By [L4], $\mathbb{E}[Y]<q(2t\delta {)}^2=4q{t}^2{\delta }^2\le t\mathrm{/}2$. Applying [L5] and step 6.3, the graph $G$ has at least $\frac{1}{2}(n\mathrm{/}(2t){)}^k$ homogeneous $k$-vertex sets.

Because $ϵ<1\mathrm{/}2$, step 4.1 gives $\mathrm{\ell }=\lceil d\log (1\mathrm{/}ϵ)\mathrm{/}ϵ\rceil \ge 2$. Using step 6.2 and step 7.1, we obtain

Since $ϵ$ and the nonempty graph $G$ were arbitrary, the exponent $d$ from step 3.1 witnesses that $\mathcal{F}$ is viral.