Alon–Pach–Solymosi: if $H_1$ and $H_2$ have the Erdős–Hajnal property, so does the graph obtained from $H_1$ by substituting $H_2$ for a vertex

Choose Erdős–Hajnal constants ${ϵ}_1>0$ for the class of $H_1$-free graphs and ${ϵ}_2>0$ for the class of $H_2$-free graphs, and set $\beta =1\mathrm{/}(2(h+1))$, ${ϵ}_0=\beta \min \{{ϵ}_1,{ϵ}_2\}$, $n_0=\max \{4\cdot {16}^h,2h,h^{2(h+1)}\}$ and $ϵ=\min \{{ϵ}_0,1\mathrm{/}{\log }_2{n}_0\}$. Then $0<\beta \le 1\mathrm{/}4$, ${ϵ}_0>0$, $n_0\ge 64$ and $ϵ>0$, and $\beta (h+1)=1\mathrm{/}2$ gives $1-\beta h=1\mathrm{/}2+\beta$.

For $a\ge 1$ and $s\le t$ one has $a^s\le a^t$, because $\log a\ge 0$ and both $\exp$ and $\log$ are increasing; and for $0<a\le b$ and $r>0$ one has $a^r\le b^r$ for the same reason.

By [L1] the class of $H$-free graphs is hereditary, so it is a class for which [F1] can supply a constant.

Let $G$ be a finite simple graph with $n=\mathrm{\mid }V(G)\mathrm{\mid }\ge n_0$ and $\mathrm{hom}(G)<n^{{ϵ}_0}$. The set of natural numbers $k$ with $k\ge n^{\beta }$ is nonempty by [L10], so it has a least element $m$ by [L11]; since $n^{\beta }>0$ we have $m\ge 1$, and $m-1<n^{\beta }$, so $n^{\beta }\le m<n^{\beta }+1\le 2n^{\beta }$, the last step because $n\ge 1$ gives $n^{\beta }\ge 1$.

Turning to the small orders, let $J$ be any nonempty $H$-free graph with $n^{\mathrm{\prime }}=\mathrm{\mid }V(J)\mathrm{\mid }<n_0$. If $n^{\mathrm{\prime }}\ge 2$ then two distinct vertices of $J$ form a clique or a stable set, so $\mathrm{hom}(J)\ge 2$; and ${n^{\mathrm{\prime }}}^{ϵ}<n_0^{ϵ}\le n_0^{1\mathrm{/}{\log }_2{n}_0}=\exp (\log n_0\cdot \log 2\mathrm{/}\log n_0)=2$, so $\mathrm{hom}(J)\ge {n^{\mathrm{\prime }}}^{ϵ}$. If $n^{\mathrm{\prime }}=1$ then $\mathrm{hom}(J)=1=1^{ϵ}$.

Since $n\ge h^{2(h+1)}=h^{1\mathrm{/}\beta }$, raising to the power $\beta$ gives $n^{\beta }\ge h$, so $m\ge h$; and $\beta \le 1\mathrm{/}4$ with $n\ge 64$ gives $m<n^{1\mathrm{/}4}+1\le n$. Hence $h\le m\le n$.

Let $W\subseteq V(G)$ with $\mathrm{\mid }W\mathrm{\mid }=m$. Then $W\mathrm{\ne }\mathrm{\varnothing }$ and $\mathrm{\mid }W{\mathrm{\mid }}^{{ϵ}_1}=m^{{ϵ}_1}\ge (n^{\beta }{)}^{{ϵ}_1}=n^{\beta {ϵ}_1}\ge n^{{ϵ}_0}>\mathrm{hom}(G)$, using ${ϵ}_0\le \beta {ϵ}_1$ and $n\ge 1$; so by [L2] the graph $G[W]$ has an induced copy of $H_1$, that is, an $h$-element $S\subseteq W$ with $G[S]\cong H_1$.

By [L3] the number $g$ of $h$-element sets $S\subseteq V(G)$ with $G[S]\cong H_1$ is at least $(n-h+1{)}^h\mathrm{/}{m}^h$, and each such $S$ carries at least one induced embedding of $H_1$ into $G$, distinct sets carrying distinct embeddings because their images differ; so ${\mathrm{ind}}_{H_1}(G)\ge g\ge (n-h+1{)}^h\mathrm{/}{m}^h>0$.

By [F4] and step 5.1 the set $\mathrm{\Phi }$ of induced embeddings of $H_1$ into $G$ is nonempty, so the set $\mathrm{\Psi }$ of [L4] is nonempty as well, since each member of $\mathrm{\Phi }$ restricts into it. Applying [L6] to the relation pairing $\phi \in \mathrm{\Psi }$ with the members of $\mathrm{\Phi }$ restricting to it, whose row fibres have sizes $\mathrm{\mid }{X}_{\phi }\mathrm{\mid }$ and whose total size is ${\mathrm{ind}}_{H_1}(G)$ by [L4], gives ${\phi }_{+}\in \mathrm{\Psi }$ with $\mathrm{\mid }{X}_{{\phi }_{+}}\mathrm{\mid }\ge {\mathrm{ind}}_{H_1}(G)\mathrm{/}\mathrm{\mid }\mathrm{\Psi }\mathrm{\mid }$.

Since $\mathrm{\mid }\mathrm{\Psi }\mathrm{\mid }\le n^{h-1}$ and $n\ge n_0\ge 2h$ gives $n-h+1>n\mathrm{/}2$, and $m<2n^{\beta }$ by step 2.1, we get $\mathrm{\mid }{X}_{{\phi }_{+}}\mathrm{\mid }\ge \frac{(n-h+1{)}^h}{m^h{n}^{h-1}}>\frac{(n\mathrm{/}2{)}^h}{2^h{n}^{\beta h}{n}^{h-1}}=\frac{n^{1-\beta h}}{4^h}=4^{-h}{n}^{1\mathrm{/}2}{n}^{\beta }$.

From $n\ge 4\cdot {16}^h$ we get $n^{1\mathrm{/}2}\ge 2\cdot 4^h$, so $4^{-h}{n}^{1\mathrm{/}2}\ge 2$ and step 7.1 gives $\mathrm{\mid }{X}_{{\phi }_{+}}\mathrm{\mid }>2n^{\beta }>m\ge n^{\beta }$. In particular $X_{{\phi }_{+}}$ is nonempty.

Therefore $\mathrm{\mid }{X}_{{\phi }_{+}}{\mathrm{\mid }}^{{ϵ}_2}\ge (n^{\beta }{)}^{{ϵ}_2}=n^{\beta {ϵ}_2}\ge n^{{ϵ}_0}>\mathrm{hom}(G)$, so by [L2] the graph $G[X_{{\phi }_{+}}]$ has an induced copy of $H_2$; the corresponding induced embedding has image inside $X_{{\phi }_{+}}$ and, adjacency in $G[X_{{\phi }_{+}}]$ agreeing with adjacency in $G$, it is an induced embedding of $H_2$ into $G$.

By [L5] applied to ${\phi }_{+}$ and that embedding, the graph $G$ of step 2.1 has an induced copy of $H$ and so is not $H$-free. Hence an $H$-free graph $G$ with $\mathrm{\mid }V(G)\mathrm{\mid }=n\ge n_0$ cannot satisfy $\mathrm{hom}(G)<n^{{ϵ}_0}$, and therefore satisfies $\mathrm{hom}(G)\ge n^{{ϵ}_0}\ge n^{ϵ}$, the last inequality by step 1.2 and $ϵ\le {ϵ}_0$.

Steps 10.1 and 2.2 together give $\mathrm{hom}(G)\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{ϵ}$ for every nonempty $H$-free graph $G$, whatever its order, and the class of $H$-free graphs is hereditary by step 1.3; that is, $ϵ$ is an Erdős–Hajnal constant for it and $H$ has the Erdős–Hajnal property.