Induced Subgraph Density. I. A loglog Step Towards Erd̋s–Hajnal

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|ᶜ, and they proved that this is true with |G|ᶜ replaced by 2c√log |G|. Until now, there has been no improvement on this result (for general H). We prove a strengthening: that for every graph H, there exists $c>0$ such that every H-free graph G with |G|≥ 2 has a clique or stable set of size at least align* &2c√log |G|loglog|G|.align* Indeed, we prove the corresponding strengthening of a theorem of Fox and Sudakov, which in turn was a common strengthening of theorems of Rödl, Nikiforov, and the theorem of Erd̋s and Hajnal mentioned above.