### The critical window for the classical Ramsey-Turán problem

[Update: Po-Shen Loh gave a wonderful talk in Banff about our paper. Here is the video.]

Jacob Fox, Po-Shen Loh and I recently uploaded to the arXiv our new paper “The critical window for the classical Ramsey-Turán problem.” This paper revisits the following celebrated Ramsey-Turán result first proved by Szemerédi in 1972.

Theorem 1 (Szemerédi 1972) For every ${\epsilon > 0}$, there exists a ${\delta > 0}$ such that any graph on ${n}$ vertices containing no 4-clique and no independent set of size greater than ${\delta n}$ has at most ${(1/8 + \epsilon)n^2}$ edges.

Turán’s theorem tells us that if we just want to construct a ${K_4}$-free graph on ${n}$ vertices with the largest possible number of edges, then we should divide the ${n}$ vertices into three nearly-equal parts and put in all possible edges across parts. This yields roughly ${n^2/3}$ edges. However, this graph contains very large independent sets with ${n/3}$ vertices. So the independent set restriction (which gives the “Ramsey” part of Ramsey-Turán) rules out this construction and forces the optimal graphs to take on a very different structure.

At the time of Szemerédi’s 1972 result, most people believed that a ${K_4}$-free graph with largest independent set of size ${o(n)}$ has to be much more sparse, perhaps with only ${o(n^2)}$ edges. So it was a surprise when, four years later, Bollobás and Erdős gave a clever geometric construction, based on the isoperimetric inequality for the high dimensional sphere, that showed that the bound given by Szemerédi is essentially optimal.

Theorem 2 (Bollobás and Erdős 1976) There exists a ${K_4}$-free graph on ${n}$ vertices with largest independent set of size ${o(n)}$ and having ${(1/8 - o(1))n^2}$ edges.

Bollobás and Erdős asked what happens in the critical window, when the number of edges is about ${n^2/8}$. This problem has received considerable attention (e.g., it was featured in a paper by Erdős from 1990 titled “Some of my favourite unsolved problems”). One of the difficulties here is that Szemerédi’s original proof used the regularity lemma, which is a powerful tool but one that unfortunately gives very poor parameter dependencies. To obtain results for the Ramsey-Turán problem at the desired precision, a regularity-free proof is needed. We give a new proof of the classical Ramsey-Turán result that avoids the use of regularity. This allows us to obtain much better and in fact nearly-optimal dependencies for the classical Ramsey-Turán problem in the critical window near ${n^2/8}$ edges, and solve several longstanding open problems in this area.