Problem Statement
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$?
Categories:
Graph Theory
Progress
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].Source: erdosproblems.com/22 | Last verified: January 13, 2026