All Random Solved Random Open
Does there exist some constant $c>0$ such that if $G$ is a graph with $n$ vertices and $\geq (1/8-c)n^2$ edges then $G$ must contain either a $K_4$ or an independent set on at least $n/\log n$ vertices?
A problem of Erdős, Hajnal, Simonovits, Sós, and Szemerédi [EHSSS93]. In other words, if $\mathrm{rt}(n;k,\ell)$ is the Ramsey-Turán number then is it true that \[\mathrm{rt}(n; 4,n/\log n)< (1/8-c)n^2?\] Erdős, Hajnal, Sós, and Szemerédi [EHSS83] proved that for any fixed $\epsilon>0$ \[\mathrm{rt}(n; 4,\epsilon n)< (1/8+o(1))n^2.\] Sudakov [Su03] proved that \[\mathrm{rt}(n; 4,ne^{-f(n)})=o(n^2)\] whenever $f(n)/\sqrt{\log n}\to \infty$.

Resolved by Fox, Loh, and Zhao [FLZ15] who showed that the answer is no; in fact they prove that \[\mathrm{rt}(n; 4, ne^{-f(n)})\geq (1/8-o(1))n^2\] whenever $f(n) =o(\sqrt{\log n/\log\log n})$.

See also [22] and the entry in the graphs problem collection.

Additional thanks to: Mehtaab Sawhney