Problem Statement
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?
Categories:
Graph Theory Ramsey Theory
Progress
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.
Source: erdosproblems.com/615 | Last verified: January 15, 2026