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

IBS Discrete Mathematics Group
Virtual Discrete Math Colloquium
Paul Seymour, The Erdős-Hajnal conjecture is true for excluding a five-cycle
December 30 2020, Wednesday @ 10:00 AM ~ 11:00 AM, Virtual via Zoom
Speaker
Paul Seymour
Princeton University
www.math.princ...
In an n-vertex graph, there must be a clique or stable set of size at least , 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 positive c such that every H-free graph has a clique or stable set of size at least (“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 positive c 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 . (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.