Sophie Spirkl

The Erdős-Hajnal conjecture states that for every graph HH there exists c>0c>0 such that every nn-vertex graph GG either contains HH as an induced subgraph, or has a clique or stable set of size at least nc.nc. I will talk about a proof of this conjecture for the case H=C5H=C5 (a five-cycle), and related results. The proof is based on an extension of a lemma about bipartite graphs due to Pach and Tomon.
This is joint work with Maria Chudnovsky, Alex Scott, and Paul Seymour.
Sophie Spirkl
University of Waterloo
Wed, 03/03/2021 - 11:30am
Zoom meeting (see below)