Paul Seymour, A loglog step towards the Erdős-Hajnal conjecture

In 1977, Erdős and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G|^c$; and they proved that this is true with $|G|^c$ replaced by $2^{c\sqrt{\log |G|}}$.

There has no improvement on this result (for general $H$) until now, but now we have an improvement: that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique or stable set of size at least $$2^{c\sqrt{\log |G|\log\log|G|}}.$$ This talk will outline the proof.

Joint work with Matija Bucić, Tung Nguyen and Alex Scott.