Polynomial Rödl, Virality and Erdős–Hajnal Equivalence

Call a set $X\in [V(G){]}^{2t}$ good when it contains a $t$-element subset $T$ with $G[T]\in \mathcal{C}$; by hypothesis, there are at least $\frac{1}{2}\left(\genfrac{}{}{0px}{}{n}{2t}\right)$ good sets.

If $X$ is good, choose $T\subseteq X$ with $\mathrm{\mid }T\mathrm{\mid }=t$ and $G[T]\in \mathcal{C}$; then [L1] gives a homogeneous $k$-element subset $K\subseteq T$, and since $G[T]$ is the induced subgraph on $T$, that same set $K$ is homogeneous in $G$.

Let $R$ be the relation between the homogeneous $k$-element subsets $K$ of $V(G)$ and the good sets $X\in [V(G){]}^{2t}$ defined by $K\subseteq X$. Step 1.2 shows that every good $X$ is related to at least one $K$, so [L4] gives $\mathrm{\mid }R\mathrm{\mid }\ge \frac{1}{2}\left(\genfrac{}{}{0px}{}{n}{2t}\right)$.

For the relation $R$ of step 2.1, fix a homogeneous $k$-element subset $K$ of $V(G)$. The good sets $X$ with $K\subseteq X$ are among the $2t$-element supersets of $K$, and [L3] counts those as $\left(\genfrac{}{}{0px}{}{n-k}{2t-k}\right)$. If $N$ is the number of homogeneous $k$-element subsets of $V(G)$, then [L4] gives $\mathrm{\mid }R\mathrm{\mid }\le N\left(\genfrac{}{}{0px}{}{n-k}{2t-k}\right)$.

Comparing steps 2.1 and 3.1 yields $N\ge \frac{1}{2}\left(\genfrac{}{}{0px}{}{n}{2t}\right)\mathrm{/}\left(\genfrac{}{}{0px}{}{n-k}{2t-k}\right)=\frac{1}{2}\left(\genfrac{}{}{0px}{}{n}{k}\right)\mathrm{/}\left(\genfrac{}{}{0px}{}{2t}{k}\right)$.

Since $n\ge 2t$, each factor in the ratio formula satisfies $(n-j)\mathrm{/}(2t-j)\ge n\mathrm{/}(2t)$ for $0\le j<k$, so $\left(\genfrac{}{}{0px}{}{n}{k}\right)\mathrm{/}\left(\genfrac{}{}{0px}{}{2t}{k}\right)\ge (n\mathrm{/}(2t){)}^k$. Therefore $N\ge \frac{1}{2}(n\mathrm{/}(2t){)}^k$.

Since $Y$ is nonnegative and $\mathbb{E}[Y]\le t\mathrm{/}2$, [L3] gives $\mathbb{P}(Y\ge t)\le 1\mathrm{/}2$, so with probability at least $1\mathrm{/}2$ one has $Y<t$.

Fix a set $X\in [V(G){]}^{2t}$ with $Y(X)<t$. For each induced embedding counted by $Y(X)$ choose one vertex from its image; this is possible because every graph in $\mathcal{F}$ has at least one vertex. Delete from $X$ every chosen vertex. Since fewer than $t$ embeddings were counted, fewer than $t$ vertices are deleted, so at least $t$ vertices remain.

Let $T$ be any $t$-element subset of the remaining vertices. If some $H\in \mathcal{F}$ had an induced embedding into $G[T]$, then that same embedding would already have been counted in $Y(X)$, so step 2.1 would have deleted a vertex from its image. Because the image lies in $T$, this contradicts the choice of $T$. Thus $G[T]$ is $\mathcal{F}$-free by [L1].

Steps 2.1 and 3.1 show that with probability at least $1\mathrm{/}2$, a uniformly random $2t$-element subset of $V(G)$ contains a $t$-element induced subgraph that is $\mathcal{F}$-free. Applying [L4] to the class of $\mathcal{F}$-free graphs proves the claimed lower bound on homogeneous $k$-sets.

[base] If $\mathrm{\ell }=0$, then the hypothesis $(1-ϵ{)}^{\mathrm{\ell }}n\le u$ reads $n\le u$. Every stable $k$-set is a $k$-element subset of the $n$-vertex set, so there are at most $\left(\genfrac{}{}{0px}{}{n}{k}\right)\le \left(\genfrac{}{}{0px}{}{u}{k}\right)=\left(\genfrac{}{}{0px}{}{n}{0}\right)\left(\genfrac{}{}{0px}{}{u}{k}\right)$ of them by [L2].

[ih] Assume $\mathrm{\ell }\ge 1$ and that the claim holds for every admissible parameter tuple with smaller value of $\mathrm{\ell }+n$.

If $u\ge n$, then every stable $k$-set is a $k$-element subset of the $n$-vertex set, so there are at most $\left(\genfrac{}{}{0px}{}{n}{k}\right)\le \left(\genfrac{}{}{0px}{}{n}{\mathrm{\ell }}\right)\left(\genfrac{}{}{0px}{}{n-\mathrm{\ell }}{k-\mathrm{\ell }}\right)\le \left(\genfrac{}{}{0px}{}{n}{\mathrm{\ell }}\right)\left(\genfrac{}{}{0px}{}{u}{k-\mathrm{\ell }}\right)$ of them by [L2]. Thus the claim is immediate in this case. We may therefore assume $u<n$. Take $v\in V(G)$ of maximum degree. Applying the hypothesis to $S=V(G)$ gives ${\mathrm{deg}}_G(v)\ge ϵn-1$. Let $U:=V(G)\setminus (\{v\}\cup N_G(v))$, so $\mathrm{\mid }U\mathrm{\mid }\le (1-ϵ)n$.

Stable $k$-sets containing $v$ correspond exactly to stable $(k-1)$-sets of $G[U]$. Since $(1-ϵ{)}^{\mathrm{\ell }-1}\mathrm{\mid }U\mathrm{\mid }\le (1-ϵ{)}^{\mathrm{\ell }}n\le u$, the induction hypothesis applied to $G[U]$ with parameters $(\mathrm{\ell }-1,k-1)$ shows that there are at most $\left(\genfrac{}{}{0px}{}{\mathrm{\mid }U\mathrm{\mid }}{\mathrm{\ell }-1}\right)\left(\genfrac{}{}{0px}{}{u}{k-\mathrm{\ell }}\right)\le \left(\genfrac{}{}{0px}{}{n-1}{\mathrm{\ell }-1}\right)\left(\genfrac{}{}{0px}{}{u}{k-\mathrm{\ell }}\right)$ such stable sets.

Stable $k$-sets avoiding $v$ are stable $k$-sets of $G-v$. Any subset of $V(G-v)$ with at least $u$ vertices is also a subset of $V(G)$, so it still satisfies the maximum-degree hypothesis. The induction hypothesis applied to $G-v$ with parameters $(\mathrm{\ell },k)$ therefore bounds their number by $\left(\genfrac{}{}{0px}{}{n-1}{\mathrm{\ell }}\right)\left(\genfrac{}{}{0px}{}{u}{k-\mathrm{\ell }}\right)$.

Adding the bounds from steps 2.1 and 2.2 and using Pascal's rule from [L2] gives at most $(\left(\genfrac{}{}{0px}{}{n-1}{\mathrm{\ell }-1}\right)+\left(\genfrac{}{}{0px}{}{n-1}{\mathrm{\ell }}\right))\left(\genfrac{}{}{0px}{}{u}{k-\mathrm{\ell }}\right)=\left(\genfrac{}{}{0px}{}{n}{\mathrm{\ell }}\right)\left(\genfrac{}{}{0px}{}{u}{k-\mathrm{\ell }}\right)$ stable $k$-sets in $G$, in the sense of [L1]. If $G$ has no $ϵ$-sparse induced subgraph on $u$ or more vertices, then [L3] shows that every such induced subgraph has a vertex of degree exceeding $ϵ\mathrm{\mid }S\mathrm{\mid }$, hence in particular at least $ϵ\mathrm{\mid }S\mathrm{\mid }-1$, so the same bound applies in that situation as well.

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.

Choose an exponent $d\ge 1$ witnessing the viral property of $\mathcal{F}$.

Let $ϵ\in (0,\frac{1}{2})$ and let $G$ be a nonempty $\mathcal{F}$-free graph. Then [L2] gives ${\mathrm{ind}}_H(G)=0<({ϵ}^d\mathrm{\mid }V(G)\mathrm{\mid }{)}^{\mathrm{\mid }V(H)\mathrm{\mid }}$ for every $H\in \mathcal{F}$.

Applying the viral implication from step 1.1 to the graph $G$ of step 1.2 yields an $ϵ$-restricted vertex set of size at least ${ϵ}^d\mathrm{\mid }V(G)\mathrm{\mid }$. This is exactly the polynomial Rödl conclusion of [L3].

Put $c:=1\mathrm{/}(2d+2)$, and let $G$ be a nonempty $\mathcal{F}$-free graph on $n$ vertices. We show that $\mathrm{hom}(G)\ge n^c$.

If $n=1$, then $\mathrm{hom}(G)=1=n^c$. If $2\le n<2^{1\mathrm{/}c}$, then any two vertices of $G$ are adjacent or nonadjacent, so $\mathrm{hom}(G)\ge 2>n^c$. It therefore remains only to treat the case $n\ge 2^{1\mathrm{/}c}=2^{2d+2}$.

Assume now that $n\ge 2^{2d+2}$ and set $ϵ:=n^{-1\mathrm{/}(d+1)}=n^{-2c}$. Then $ϵ\in (0,\frac{1}{2})$. By [L1], choose an $ϵ$-restricted vertex set $X\subseteq V(G)$ with $\mathrm{\mid }X\mathrm{\mid }\ge {ϵ}^{d}n=n^{1-d\mathrm{/}(d+1)}=n^{1\mathrm{/}(d+1)}=n^{2c}$.

Suppose first that $X$ is $ϵ$-sparse. By [L3], the induced graph $G[X]$ has maximum degree at most $ϵ\mathrm{\mid }X\mathrm{\mid }$, so [L4] gives $\chi (G[X])\le ϵ\mathrm{\mid }X\mathrm{\mid }+1\le 2ϵ\mathrm{\mid }X\mathrm{\mid }$ because $ϵ\mathrm{\mid }X\mathrm{\mid }\ge ϵn^{2c}=1$. Applying the second inequality of [L4] to $G[X]$ yields $\mathrm{\mid }X\mathrm{\mid }\le \chi (G[X])\alpha (G[X])\le 2ϵ\mathrm{\mid }X\mathrm{\mid }\alpha (G[X])$, so $\alpha (G[X])\ge 1\mathrm{/}(2ϵ)=n^{2c}\mathrm{/}2\ge n^c$, the last inequality using $n^c\ge 2$ from step 2.1. Hence $\mathrm{hom}(G)\ge n^c$.

Suppose instead that $X$ is $ϵ$-dense. Then [L5] makes $X$ $ϵ$-sparse in $\bar{G}$, so the same calculation as in step 3.1 applied to $\bar{G}[X]$ yields a stable set of size at least $n^c$ in $\bar{G}[X]$. By [L5], that stable set is a clique of size at least $n^c$ in $G[X]$, and again $\mathrm{hom}(G)\ge n^c$.

Step 2.1 handles $n<2^{1\mathrm{/}c}$, and steps 3.1 and 4.1 handle the large-$n$ case. Thus every nonempty $\mathcal{F}$-free graph $G$ satisfies $\mathrm{hom}(G)\ge \mathrm{\mid }V(G){\mathrm{\mid }}^c$, so [L2] shows that $c=1\mathrm{/}(2d+2)$ is an Erdős–Hajnal constant.

Assertion 1 implies assertion 3 by [L1].

Assertion 3 implies assertion 2 by [L2].

Assertion 2 implies assertion 1 by [L3].

The three implications close the cycle $1\Rightarrow 3\Rightarrow 2\Rightarrow 1$, so the three assertions are equivalent.

Applying [L1] to the family $\{H\}$ gives the equivalence of the finite-family Erdős–Hajnal property, the finite-family polynomial Rödl property, and virality for $\{H\}$.

By [L2] and [L3], the first of those assertions is exactly “$H$ has the Erdős–Hajnal property”, while the other two are already assertions about the singleton family $\{H\}$.

Steps 1.1 and 1.2 give the claimed equivalence.

By [L3], the graph $P_3$ has three vertices, so [L1] gives the Erdős–Hajnal property for $P_3$.

Applying [L2] to the graph $P_3$ of step 1.1 shows that the singleton family $\{P_3\}$ is viral.