OPEN

Is it true that any graph $K_r$-free graph on $n$ vertices with average degree $t$ contains an independent set on
\[\gg_r \frac{\log t}{t}n\]
many vertices?

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$.