The Erdős–Hajnal Property and Homogeneous Sets

Let $G\in \mathcal{C}$ be nonempty and put $n=\mathrm{\mid }V(G)\mathrm{\mid }\ge 1$.

If $n=1$, then $n^{\delta }=n^{ϵ}=1$, so the required inequality follows from the one for $ϵ$.

If $n>1$, then $\log n>0$ by [L2], and hence $\delta \log n\le ϵ\log n$.

In the case $n>1$, [L3] and the real-power convention in [L1] give $n^{\delta }=\exp (\delta \log n)\le \exp (ϵ\log n)=n^{ϵ}$.

In both cases, $\mathrm{hom}(G)\ge n^{ϵ}\ge n^{\delta }$; since $G$ was arbitrary, $\delta$ is an Erdős–Hajnal constant for $\mathcal{C}$.

Put $k=\lfloor \frac{1}{2}{\log }_{2}n\rfloor +1$. Then $k$ is a positive integer, $k>\frac{1}{2}{\log }_{2}n$, and $2k-2\le {\log }_{2}n$.

By [L5], $\log 2>\log 1=0$, so $2k-2\le {\log }_{2}n=\log n\mathrm{/}\log 2$ gives $(2k-2)\log 2\le \log n$. Applying $\log (xy)=\log x+\log y$ to the $2k-2$ factors of $2^{2k-2}$ gives $\log (2^{2k-2})=(2k-2)\log 2\le \log n$, and $\log$ is strictly increasing, so $2^{2k-2}\le n$.

The $(k-1)$-subsets of a $(2k-2)$-set form part of its power set, and binary membership choices give the power set $2^{2k-2}$ elements, so $\left(\genfrac{}{}{0px}{}{2k-2}{k-1}\right)\le 2^{2k-2}\le n$.

Apply [L2] with $s=t=k$: $G$ has a clique or stable set of order at least $k$.

Therefore $\mathrm{hom}(G)\ge k>\frac{1}{2}{\log }_{2}n$ by [L1], which proves the stated weak inequality; when $n=1$, this reads $1\ge 0$ and the same argument has $k=1$.

By [L3], ${\mathcal{C}}_t$ is hereditary. If $t=1$, it has no nonempty member, so any positive exponent works in [L2]; if $t=2$, every member is empty by [L3] and [L4], so $\mathrm{hom}(G)=\mathrm{\mid }V(G)\mathrm{\mid }$ and exponent $1$ works.

Assume $t\ge 3$. For all sufficiently large integers $n$, the integer $s=\lfloor \frac{1}{2}{n}^{1\mathrm{/}(t-1)}\rfloor$ satisfies $s\ge t-2$, $s\ge n^{1\mathrm{/}t}$, and $s\ge 1$; these assertions follow from [L7], [L8], and [L9] because $n^{1\mathrm{/}(t-1)}\mathrm{/}{n}^{1\mathrm{/}t}=n^{1\mathrm{/}(t(t-1))}$ tends to infinity.

For such $n$, $t+s-2\le 2s$, and hence $\left(\genfrac{}{}{0px}{}{t+s-2}{t-1}\right)\le (t+s-2{)}^{t-1}\le (2s{)}^{t-1}\le n$; the first inequality counts ordered choices containing every $(t-1)$-subset.

If $G\in {\mathcal{C}}_t$ has sufficiently large order $n$, [L5] with parameters $(t,s)$ and step 2.1 give a $t$-clique or an $s$-vertex stable set; the first is forbidden, so $\mathrm{hom}(G)\ge \alpha (G)\ge s\ge n^{1\mathrm{/}t}$.

Choose an integer threshold $N\ge 2$ beyond which step 3.1 applies, and choose $0<ϵ\le 1\mathrm{/}t$ so small that $N^{ϵ}\le 2$. Such an $ϵ$ exists by [L7], [L8], and [L9].

If $G\in {\mathcal{C}}_t$ has $n\ge N$, then $\mathrm{hom}(G)\ge n^{1\mathrm{/}t}\ge n^{ϵ}$; if $2\le n<N$, an edge gives a two-vertex clique and a nonedge gives a two-vertex stable set, so $\mathrm{hom}(G)\ge 2\ge n^{ϵ}$; and if $n=1$, both sides equal $1$. Thus $ϵ$ is an Erdős–Hajnal constant for ${\mathcal{C}}_t$.

If $G$ is null, then $\mathrm{hom}(G)=0=\sqrt{0}$ by [L1] and [L8]. Assume henceforth that $G$ is nonempty.

Every connected component of $G$ is a clique: otherwise two nonadjacent vertices in one component have a shortest path $v_0,\dots ,v_{\mathrm{\ell }}$ with $\mathrm{\ell }\ge 2$; the vertices $v_0,v_1,v_2$ are distinct, the consecutive pairs are edges, and $v_0{v}_2$ is not an edge because it would shorten the path, so they induce $P_3$, contrary to [L3].

Let $r\ge 1$ be the number of connected components of $G$. Choosing one vertex from each of these finitely many nonempty components gives a stable set, since an edge would put its endpoints in one component; hence $\alpha (G)\ge r$.

Let the component orders be $c_1,\dots ,c_r$. By [L6], $r\ge 1$, each $c_i\ge 1$, and $\mathrm{\mid }V(G)\mathrm{\mid }={\sum }_i{c}_i$; step 1.2 gives $\omega (G)\ge {\max }_i{c}_i$.

Therefore $\mathrm{\mid }V(G)\mathrm{\mid }={\sum }_i{c}_i\le r{\max }_i{c}_i\le \alpha (G)\omega (G)\le \mathrm{hom}(G{)}^2$.

Both sides are nonnegative, so [L8] and step 3.1 yield $\mathrm{hom}(G)\ge \sqrt{\mathrm{\mid }V(G)\mathrm{\mid }}=\mathrm{\mid }V(G){\mathrm{\mid }}^{1\mathrm{/}2}$. Together with [L2] and [L3], this makes $1\mathrm{/}2$ an Erdős–Hajnal constant for the $P_3$-free class.

By [L8], $\log 2>\log 1=0$, so [L7] makes ${\log }_2=\log \mathrm{/}\log 2$ strictly increasing with ${\log }_{2}1=0$. Applying $\log (xy)=\log x+\log y$ to the factors of an integer power, and $\log (1\mathrm{/}x)=-\log x$ for a negative exponent, gives ${\log }_2(2^m)=m$ for every integer $m$ and ${\log }_2(x^j)=j{\log }_{2}x$ for every $x>0$ and every positive integer $j$.

Since $n\ge 16=2^4$, step 1.1 gives $L:={\log }_{2}n\ge 4$, and $k=\lceil 3L\rceil$ satisfies $k\ge 3L\ge 12$.

In $G(n,1\mathrm{/}2)$ let $X$ count the $k$-subsets that induce a clique or a stable set. For a fixed $k$-subset these two disjoint events each prescribe all $\left(\genfrac{}{}{0px}{}{k}{2}\right)$ pairs, so [L2] and [L3] give probability $2\cdot 2^{-\left(\genfrac{}{}{0px}{}{k}{2}\right)}$.

By [L4] and [L6], $\mathbb{E}X=2\left(\genfrac{}{}{0px}{}{n}{k}\right)2^{-k(k-1)\mathrm{/}2}\le 2n^k{2}^{-k(k-1)\mathrm{/}2}$.

By step 1.1 the base-two logarithm of that last bound is $1+kL-k(k-1)\mathrm{/}2=1+k(L-(k-1)\mathrm{/}2)\le 1+3L(1-L)\mathrm{/}2<0$, where the first inequality uses $k\ge 3L$ and $L\ge 4$, which make $L-(k-1)\mathrm{/}2\le (1-L)\mathrm{/}2<0$. Since ${\log }_2$ is strictly increasing with ${\log }_{2}1=0$, the bound itself is below $1$, so $\mathbb{E}X<1$.

By [L5], choose an outcome graph $G$ with $X=0$. It has no homogeneous $k$-subset, and any homogeneous set of order at least $k$ would contain one, so $\mathrm{hom}(G)\le k-1<3L=3{\log }_{2}n$.

Suppose, for contradiction, that $\mathcal{G}$ has an Erdős–Hajnal constant $ϵ>0$.

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

Choose from [L2] an $n$-vertex graph $G$ with $\mathrm{hom}(G)<3{\log }_{2}n<n^{ϵ}$, contradicting [L1] and step 1.1. Therefore $\mathcal{G}$ does not have the Erdős–Hajnal property.

By [L3], both classes in the statement are hereditary, and [L4] gives $\mathrm{hom}(\bar{G})=\mathrm{hom}(G)$ for every $G$.

Let $ϵ$ be a constant for $\mathcal{C}$ and let $F\in \bar{\mathcal{C}}$ be nonempty. Then $\bar{F}\in \mathcal{C}$ by [L2], while $\mathrm{\mid }V(\bar{F})\mathrm{\mid }=\mathrm{\mid }V(F)\mathrm{\mid }$ and $\mathrm{hom}(\bar{F})=\mathrm{hom}(F)$ by step 1.1, so [L1] gives $\mathrm{hom}(F)\ge \mathrm{\mid }V(F){\mathrm{\mid }}^{ϵ}$.

Thus every constant of $\mathcal{C}$ is a constant of $\bar{\mathcal{C}}$; applying the same argument to $\bar{\mathcal{C}}$ and using $\overline{\stackrel{‾}{G}}=G$ gives the reverse inclusion of constant sets.

By [L5], complementation bijects the $H$-free class with the $\bar{H}$-free class, so step 3.1 gives the fixed-pattern consequence.

[assume-case null] If $\mathrm{\mid }V(H)\mathrm{\mid }=0$, every graph contains the unique empty induced embedding of $H$, so the $H$-free class has no members and [L1] is vacuously satisfied by every positive exponent.

[assume-case nonnull] Suppose $1\le \mathrm{\mid }V(H)\mathrm{\mid }\le 3$. Up to isomorphism and complementation, $H$ is one of $K_1,K_2,K_3$, or $P_3$: this follows by the edge count for orders at most two, and for order three by separating the cases of zero, one, two, or three edges.

Each complete case has the property by [L2], the path case has it by [L3], and every complementary case has it by [L4].

The cases are exhaustive, so every graph on at most three vertices has the Erdős–Hajnal property.

Every nonempty $G\in \mathcal{D}$ also lies in $\mathcal{C}$, so [L1] gives $\mathrm{hom}(G)\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{ϵ}$.

Thus $ϵ$ is a constant for $\mathcal{D}$; the existence assertion follows by retaining any constant of $\mathcal{C}$.

If $G$ is $H$-free, then it is $H^{\mathrm{\prime }}$-free: an induced embedding $H^{\mathrm{\prime }}{\hookrightarrow }_{\mathrm{i}\mathrm{n}\mathrm{d}}G$ would compose with the Given embedding to put $H$ inducedly in $G$.

Hence the $H$-free class is a subclass of the $H^{\mathrm{\prime }}$-free class, and both are hereditary by [L4].

Applying [L1] proves that every constant of $H^{\mathrm{\prime }}$ is a constant of $H$, and therefore proves the property implication.

Assume assertion 1, let $\mathcal{F}$ be finite and nonempty, and choose $H\in \mathcal{F}$. By [L2], every $\mathcal{F}$-free graph is $H$-free.

Conversely, assume assertion 2 and let $H$ be any finite graph. Applying assertion 2 to the finite nonempty family $\{H\}$ gives the property for the $H$-free class, which is assertion 1 by [L1] and [L2].

The $H$-free class has the property by assertion 1 and [L1], so its hereditary subclass of $\mathcal{F}$-free graphs has it by [L3]. This proves assertion 2.

The two implications prove the equivalence.