PROVED
This has been solved in the affirmative.
Let $\epsilon>0$ and $n$ be sufficiently large depending on $\epsilon$. Is there a graph on $n$ vertices with $\geq n^2/8$ many edges which contains no $K_4$ such that the largest independent set has size at most $\epsilon n$?
In other words, if $\mathrm{rt}(n;k,\ell)$ is the Ramsey-Turán number then is it true that (for sufficiently large $n$)\[\mathrm{rt}(n; 4,\epsilon n)\geq n^2/8?\]Conjectured by Bollobás and Erdős
[BoEr76], who proved the existence of such a graph with $(1/8+o(1))n^2$ many edges. Solved by Fox, Loh, and Zhao
[FLZ15], who proved that for every $n\geq 1$ there exists a graph on $n$ vertices with $\geq n^2/8$ many edges, containing no $K_4$, whose largest independent set has size at most\[ \ll \frac{(\log\log n)^{3/2}}{(\log n)^{1/2}}n.\]See also
[615].
View the LaTeX source
Additional thanks to: Mehtaab Sawhney
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #22, https://www.erdosproblems.com/22, accessed 2026-02-13
