Tag: PaulSeymour

In 1977, Erdős and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G{|}^c$; and they proved that this is true with $|G{|}^c$ replaced by $2^{c\sqrt{\log |G|}}$.

There has no improvement on this result (for general $H$) until now, but now we have an improvement: that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique or stable set of size at least $$2^{c\sqrt{\log |G|\log \log |G|}}.$$ This talk will outline the proof.

Joint work with Matija Bucić, Tung Nguyen and Alex Scott.

The Gyárfás-Sumner conjecture says that for every forest $H$, there is a function $f$ such that the chromatic number $\chi (G)$ is at most $f(\omega (G))$ for every $H$-free graph $G$ (“$H$-free” means with no induced subgraph isomorphic to $H$, and $\omega (G)$ is the size of the largest clique of $G$). This well-known conjecture has been proved only for a few types of forest.

Nevertheless, there is a much stronger conjecture, due to Esperet: that for every forest $H$, there is a polynomial function $f$ as above. As one might expect, this has been proved for even fewer types of forest; and the smallest tree $H$ for which Esperet’s conjecture is not known is the five-vertex path $P_5$.

A third notorious conjecture is the Erdős-Hajnal conjecture, that for every graph $H$, there exists $c>0$ such that $\alpha (G)\omega (G)\ge |G{|}^c$ for every $H$-free graph $G$ (where $\alpha (G)$ is the size of the largest stable set of $G$). The smallest graph $H$ for which this is not known is also $P_5$, which, conveniently, is a forest; and every forest that satisfies Esperet’s conjecture also satisfies the Erdős-Hajnal conjecture. So there is substantial interest in the chromatic numbers of $P_5$-free graphs. The best upper bound that was previously known, due to Esperet, Lemoine, Maffray, and Morel, was that $\chi (G)\le (5/27)3^{\omega }(G)$ for every $P_5$-free graph $G$ with $\omega (G)>2$. In recent work with Alex Scott and Sophie Spirkl, we have proved several results related to Esperet’s conjecture, including proofs of its truth for some new types of forest $H$, and a “near-polynomial” bound when $H=P_5$, that $\chi (G)\le \omega (G{)}^{{\log }_2(\omega (G))}$ for every $P_5$-free graph $G$ with $\omega (G)>2$. We survey these results and give a proof of the new bound for $P_5$.

In an n-vertex graph, there must be a clique or stable set of size at least $C\log n$, and there are graphs where this bound is attained. But if we look at graphs not containing a fixed graph H as an induced subgraph, the largest clique or stable set is bigger.

Erdős and Hajnal conjectured in 1977 that for every graph H, there exists c>0 such that every H-free graph has a clique or stable set of size at least $|G{|}^c$ (“H-free” means not containing H as an induced subgraph, and |G| means the number of vertices of G). This is still open, even for some five-vertex graphs H; and the case that has attracted most attention is when H is a cycle of length five.

It is true in that case. We will give a sketch of the proof, which is via applying a lemma about bipartite graphs, a variant of a theorem of I. Tomon.

This lemma has several other applications to the Erdős-Hajnal conjecture. For instance, it implies that for every cycle C and forest T, there exists c>0 such that every graph that is both C-free and T’-free (where T’ is the complement of T) has a clique or stable set of size $|G{|}^c$. (Until now this was open when C has length five and T is a 5-vertex path.)

Joint work with Maria Chudnovsky, Alex Scott and Sophie Spirkl.