PIMS-UVic Discrete Math Seminar: Sophie Spirkl

The Erdos-Hajnal conjecture states that for every graph H there exists $c > 0$ such that every n-vertex graph $G$ either contains $H$ as an induced subgraph, or has a clique or stable set of size at least $n^c$. I will talk about a proof of this conjecture for the case $H = 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.