Induced subgraph density. I. A loglog step towards Erdos-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 $\mathrm{\mid }G{\mathrm{\mid }}^c$; and they proved that this is true with $\mathrm{\mid }G{\mathrm{\mid }}^c$ replaced by $2^{c\sqrt{\log \mathrm{\mid }G\mathrm{\mid }}}$. 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 $\mathrm{\mid }G\mathrm{\mid }\ge 2$ has a clique or stable set of size at least $$2^{c\sqrt{\log \mathrm{\mid }G\mathrm{\mid }\log \log \mathrm{\mid }G\mathrm{\mid }}}\mathrm{.}$$ 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.