The Erdős–Hajnal Property and Homogeneous Sets — Examples

If $n=0$, both graphs are null and the assertion is [L1].

If $n>0$, all $n$ vertices form a clique in $K_n$ and a stable set in ${\bar{K}}_n$, while neither graph has a vertex set larger than its whole vertex set.

Thus the maximum in [L1] is $n$ for both graphs.

A clique uses at most one vertex from each part, while positivity of $a,b$ supplies a cross-edge, so $\omega (K_{a,b})=2$.

A stable set lies wholly in one part, and either whole part is stable, so $\alpha (K_{a,b})=\max \{a,b\}$.

Taking the maximum in [L1] gives the formula.

The pair $\{0,1\}$ is an edge and $\{0,2\}$ is a nonedge, so $C_5$ has both a two-vertex clique and a two-vertex stable set.

Any three vertices on the cycle contain a consecutive pair, hence an edge; their complement has two omitted vertices, so among the three cyclic gaps one has length at least two, giving a nonconsecutive pair and hence a nonedge. Thus no three vertices are homogeneous.

The map $i\mapsto 2i(\mathrm{m}\mathrm{o}\mathrm{d}5)$ sends consecutive differences $\pm 1$ to differences $\pm 2$, exactly the nonedges of $C_5$, so it is an isomorphism $C_5\cong \overline{C_5}$.

Steps 1.1 and 1.2 give $\omega (C_5)=\alpha (C_5)=2$, hence $\mathrm{hom}(C_5)=2$ by [L1]; step 1.3 gives self-complementarity.

Both classes are hereditary because an induced subgraph of a complete graph is complete and one of an empty graph is empty.

Every nonempty $G$ in either class has all $\mathrm{\mid }V(G)\mathrm{\mid }$ vertices homogeneous, as a clique in $\mathcal{K}$ or a stable set in $\mathcal{E}$, so $\mathrm{hom}(G)=\mathrm{\mid }V(G)\mathrm{\mid }$.

Hence $\mathrm{hom}(G)=\mathrm{\mid }V(G){\mathrm{\mid }}^1$ and [L1] gives constant $1$ for both classes; equivalently, the result for one class transfers to the other by [L4].

[assume-case small] If $N\le 1$, choose $ϵ=1$; every nonempty member has one vertex and homogeneous number $1$ by [L2].

[assume-case large] If $N\ge 2$, choose $ϵ=1$ when $N=2$, and choose $ϵ=\log 2\mathrm{/}\log N$ when $N>2$. In the latter case $\log N>\log 2>\log 1=0$ by [L3], so $ϵ>0$, and [L4] with [L5] gives $N^{ϵ}=\exp ((\log 2\mathrm{/}\log N)\log N)=\exp (\log 2)=2$.

Since $\log$ is a strictly increasing bijection onto $\mathbb{R}$ with inverse $\exp$, the function $\exp$ is strictly increasing as well; so for $1\le n\le N$ the inequality $ϵ\log n\le ϵ\log N$ gives $n^{ϵ}\le N^{ϵ}=2$ by [L4].

In the large case, a graph of order $n\ge 2$ has either an edge, which is a two-vertex clique, or a nonedge, which is a two-vertex stable set; hence $\mathrm{hom}(G)\ge 2\ge n^{ϵ}$ by step 2.1, while for $n=1$ both sides equal $1$. The given hereditary hypothesis places $\mathcal{C}$ in the domain of [L1].

The cases are exhaustive, and in each [L1] supplies the Erdős–Hajnal property.

Complementing the two edges of $P_3$ leaves the edge joining its endpoints and makes its middle vertex isolated.

By [L3], complementation maps the $P_3$-free class bijectively to the $\overline{P_3}$-free class; both are hereditary by [L4].

The equality of their constant sets now follows from [L1].

By [L2] and [L3], choose an integer $n\ge 16$ with $3{\log }_{2}n<n^{ϵ}$.

By [L1], choose an $n$-vertex graph $G$ with $\mathrm{hom}(G)<3{\log }_{2}n<n^{ϵ}$.

Thus every proposed positive universal exponent has a finite counterexample, so the statement is false.

The class of all finite graphs is closed under isomorphism and induced subgraphs, so it is hereditary by [L2].

This hereditary class fails the Erdős–Hajnal property by [L1], contradicting the asserted universal claim.