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|^c, and they proved that this is true with |G|^c replaced by 2^c√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 ₂c√log |G| log log |G| . 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.