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.