Paul Seymour gave an online talk on the recent result regarding the Erdős-Hajnal conjecture at the Virtual Discrete Math Colloquium

On December 30, 2020, Paul Seymour from Princeton University was the speaker of the Virtual Discrete Math Colloquium. He presented his recent breakthrough on the Erdős-Hajnal conjecture with Maria Chudnovsky, Alex Scott, and Sophie Spirkl, which in particular proves that the Erdős-Hajnal conjecture holds for the cycle of length 5. The title of his talk was “The Erdős-Hajnal conjecture is true for excluding a five-cycle“.

Paul Seymour, The Erdős-Hajnal conjecture is true for excluding a five-cycle

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.