A logarithmic independence bound for clique-free graphs

For every fixed integer r ≥ 4, every K${}_r$-free graph on n vertices with average degree d ≥ 2 has an independent set of size at least $c_{r}n\log d/d$, where $c_r>0$ depends only on r. This proves the fixed-clique-size independence conjecture of Ajtai, Erdős, Komlós and Szemerédi.