Erdős–Hajnal conjecture

In contrast, for random graphs in the Erdős–Rényi model with edge probability 1/2, both the maximum clique and the maximum independent set are much smaller: their size is proportional to the logarithm of ${\displaystyle n}$, rather than growing polynomially. Ramsey's theorem proves that no graph has both its maximum clique size and maximum independent set size smaller than logarithmic.[1][2] Ramsey's theorem also implies the special case of the Erdős–Hajnal conjecture when ${\displaystyle H}$ itself is a clique or independent set.[1]

This conjecture is due to Paul Erdős and András Hajnal, who proved it to be true when ${\displaystyle H}$ is a cograph. They also showed, for arbitrary ${\displaystyle H}$, that the size of the largest clique or independent set grows superlogarithmically. More precisely, for every ${\displaystyle H}$ there is a constant ${\displaystyle c}$ such that the ${\displaystyle n}$-vertex ${\displaystyle H}$-free graphs have cliques or independent sets containing at least ${\displaystyle \exp c{\sqrt {\log n}}}$ vertices.[1][3] The graphs ${\displaystyle H}$ for which the conjecture is true also include those with four verticies or less,[1][4] all five-vertex graphs except the five-vertex path and its complement,[5][1][6] and any graph that can be obtained from these and the cographs by modular decomposition.[1][2] As of 2021, however, the full conjecture has not been proven, and remains an open problem.[1]

An earlier formulation of the conjecture, also by Erdős and Hajnal, concerns the special case when ${\displaystyle H}$ is a 5-vertex cycle graph.[4] This case has been resolved by Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl in 2021.[7][8] The ${\displaystyle C_{5}}$-free graphs include the perfect graphs, which necessarily have either a clique or independent set of size proportional to the square root of their number of vertices. Conversely, every clique or independent set is itself perfect. For this reason, a convenient and symmetric reformulation of the Erdős–Hajnal conjecture is that for every graph ${\displaystyle H}$, the ${\displaystyle H}$-free graphs necessarily contain an induced perfect subgraph of polynomial size.[1]

Alon et al. [2] showed that the following statement concerning tournaments is equivalent to the Erdős-Hajnal conjecture.

Conjecture. For every tournament ${\displaystyle T}$, there exists ${\displaystyle \varepsilon (T)>0}$ and ${\displaystyle c>0}$ such that for every ${\displaystyle T}$-free tournament ${\displaystyle G}$ with ${\displaystyle n}$ vertices ${\displaystyle \chi (G)\leq c\cdot n^{1-\varepsilon }}$.

Here ${\displaystyle \chi (G)}$ denotes the chromatic number of ${\displaystyle G}$, which is the smallest ${\displaystyle k\in \mathbb {N} }$ such that there is a ${\displaystyle k}$-coloring for ${\displaystyle G}$. A coloring of a tournament ${\displaystyle G}$ is a mapping ${\displaystyle \phi :V(G)\rightarrow \{1,\ldots ,k\}}$ such that the color classes ${\displaystyle \{v\in V(T):\phi (v)=i\}}$ are transitive for all ${\displaystyle i=1,\ldots ,k}$.

The class of tournaments ${\displaystyle H}$ with the property that every ${\displaystyle H}$-free tournament ${\displaystyle G}$ has ${\displaystyle \chi (G)\leq c(H)}$ for some constant ${\displaystyle c(H)}$ satisfies this equivalent Erdős-Hajnal conjecture (with ${\displaystyle \varepsilon =1}$). Such tournaments ${\displaystyle H}$, called heroes, were considered by Berger et al.[9] There it is proven that a hero has a special structure which is as follows:

Theorem. A tournament is a hero if and only if all its strong components are heroes. A strong tournament with more than one vertex is a hero if and only if it equals ${\displaystyle \Delta (H,k,1)}$ or ${\displaystyle \Delta (H,1,k)}$ for some hero ${\displaystyle H}$ and some integer ${\displaystyle k\geq 0}$.

Here ${\displaystyle \Delta (H,k,1)}$ denotes the tournament with the three components ${\displaystyle H}$, the transitive tournament of size ${\displaystyle k}$ and a single node ${\displaystyle q}$. The arcs between the three components are defined as follows: ${\displaystyle A=\{(v,w):(v\in H\wedge w\in T_{k})\vee (v\in T_{k}\wedge w=q)\vee (v=q\wedge w\in H)\}}$. The tournament ${\displaystyle \Delta (H,1,k)}$ is defined analogously.

• The Erdös-Hajnal Conjecture, The Open Problem Garden