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 , there exists a
such that any graph on
vertices containing no 4-clique and no independent set of size greater than
has at most
edges.
Turán’s theorem tells us that if we just want to construct a -free graph on
vertices with the largest possible number of edges, then we should divide the
vertices into three nearly-equal parts and put in all possible edges across parts. This yields roughly
edges. However, this graph contains very large independent sets with
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 -free graph with largest independent set of size
has to be much more sparse, perhaps with only
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 -free graph on
vertices with largest independent set of size
and having
edges.
Bollobás and Erdős asked what happens in the critical window, when the number of edges is about . 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
edges, and solve several longstanding open problems in this area.