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

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.

Each vertex of $G$ determines one induced embedding of $K_1$ into $G$, so [L2] gives ${\mathrm{ind}}_{K_1}(G)=\mathrm{\mid }V(G)\mathrm{\mid }$.

If $d\ge 1$, then $0<ϵ<1$ gives $\log ϵ<0$ and therefore $d\log ϵ\le \log ϵ<0$. By [L3], $0<{ϵ}^d\le ϵ<1$, so ${ϵ}^d\mathrm{\mid }V(G)\mathrm{\mid }<\mathrm{\mid }V(G)\mathrm{\mid }={\mathrm{ind}}_{K_1}(G)$. Thus the defining viral inequality for $K_1$ can hold for no nonempty graph.

Since the antecedent in [L1] has no nonempty instance, every exponent $d\ge 1$ witnesses the viral implication vacuously. Therefore any finite family containing $K_1$ is viral.

The graph $G$ is $P_3$-free: three vertices in one clique induce a triangle, three vertices meeting both cliques induce either one edge or no edge, and none of those induced subgraphs is $P_3$.

Let $X:=V(G)$. Every vertex of $X$ has exactly $N-1$ neighbours and exactly $N$ non-neighbours inside $X$. Since $N>1\mathrm{/}(1-2ϵ)$, one has $N-1>2ϵN=ϵ\mathrm{\mid }X\mathrm{\mid }$, so $X$ is not $ϵ$-sparse; and because $ϵ<1\mathrm{/}2$, one also has $N>ϵ\mathrm{\mid }X\mathrm{\mid }$, so $X$ is not $ϵ$-dense. Thus $X$ is not $ϵ$-restricted by [L4].

One clique component of $G$ is $0$-dense and therefore $ϵ$-restricted, so the polynomial Rödl conclusion for $G$ is realized by a proper subset of vertices rather than by the whole graph.

By [L3], the graph $P_3$ has three vertices, so [L1] gives the Erdős–Hajnal property for $P_3$. Applying [L2] then shows that the singleton family $\{P_3\}$ has the polynomial Rödl property.

Steps 1.2 and 1.3 show that the theorem's restricted witness need not be $V(G)$ itself, refuting the claim.

By [L1], every finite graph is $\mathrm{\varnothing }$-free. So the class of $\mathrm{\varnothing }$-free graphs is exactly the class of all finite graphs.

Applying [L2] to the class identified in step 1.1 shows that the empty family does not have the Erdős–Hajnal property.

Therefore the claim is false. By [L3], the empty family also has neither of the other two equivalent properties from the A page.