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.

Read the rest of this entry »