- This event has passed.

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

## March 16 Thursday @ 10:00 AM - 11:00 AM KST

Zoom ID: 869 4632 6610 (ibsdimag)

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.