Problem #802: Is it true that any $K_r$-free graph on $n$ vertices with...

---

Progress

A conjecture of Ajtai, Erdős, Komlós, and Szemerédi [AEKS81], who proved that there must exist an independent set on\[\gg_r \frac{\log\log(t+1)}{t}n\]many vertices. Shearer [Sh95] improved this to\[\gg_r \frac{\log t}{\log\log(t+1)t}n.\]Ajtai, Komlós, and Szemerédi [AKS80] proved the conjectured bound when $r=3$. Alon [Al96b] proved the conjectured bound, but replacing the $K_r$-free assumption with the stronger assumption that the induced graph on every vertex neighbourhood has chromatic number $\leq r-2$.