Special Seminar - Paul Seymour

Title: Erdos-Hajnal meets Gyarfas-Sumner

Abstract:

The Gyarfas-Sumner conjecture says that every graph with huge (enough) chromatic number and bounded clique number contains any given forest as an induced subgraph. (And non-forests do not have this property.) The Erdos-Hajnal conjecture says that for every graph H, all graphs not containing H as an induced subgraph have a clique or stable set of polynomial size.  Both conjectures are well-known, and impossibly difficult.

This talk is about a much nicer problem vaguely related to both of these, the following.  Say an n-vertex graph is ʿʿc-coherentʾʾ if every vertex has degree <cn, and every two disjoint vertex subsets of size at least cn have an edge between them. Which graphs H have the property that all c-coherent graphs contain H if c is small enough?

The answer turns out to be forests (like the Gyarfas-Sumner conjecture, only this time we can prove it); proved in joint work with Maria Chudnovsky, Alex Scott, and Sophie Spirkl a few weeks ago.  This extends some previous theorems (Bousquet, Lagoutte, and Thomasse proved it for paths; and Liebenau, Pilipczuk, Spirkl and I proved it for subdivided caterpillars). All three proofs are quite pretty and I will sketch them if there is time.

The connection with Erdos-Hajnal is, it implies that for every forest H, all graphs that contain neither H nor its complement have two linear sets of vertices that either have no edges between or are complete to each other; and this implies that all such graphs have a polynomial-sized clique or stable set. We also have some results (the four of us with Jacob Fox) about what you can say when you exclude H and its complement, and neither of them is a forest. (You can still get two sets that are complete or anticomplete, but not such big ones.)