The critical window for the classical Ramsey-Turán problem
by Yufei Zhao
[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.
Szemerédi’s regularity lemma is a universal structural result about large dense graphs, and it acts as a powerful microscope for studying the asymptotic regimes of extremal problems. Yet this power comes at the cost of limited resolution outside of the very far asymptotic regime, as the regularity lemma’s quantitative bounds necessarily involve tower-type dependencies. An important direction of research in this area has been to find alternatives to regularity-based proofs, partly in order to obtain better bounds, but also to better understand the power and limitations of the regularity method. Szemerédi’s proof of the Ramsey-Turán problem is historically the first application of the regularity lemma. Originally the regularity implied a doubly-exponentials-type dependence of on (a weaker version of regularity was used then). A natural question is: what is the correct dependence between and ? Our regularity-free proof of this result significantly improves the dependencies of the parameters. We show that there is a linear dependence between and , which is tight up to a constant factor.
For the lower bound to the Ramsey-Turán problem, we modify the construction of Bollobás and Erdős to slightly boost the edge density to just over . We can answer the following previously open questions about the critical window.
- (Bollobás and Erdős 1976) Is it true that for each there is an such that for each sufficiently large there is a graph with vertices, independence number at most , and at least edges?
- (Bollobás and Erdős 1976) Is it true that for every , there is a -free graph with vertices, independence number , and at least edges?
- (Erdős, Hajnal, Simonovits, Sós and Szemerédi 1993) Is it true for some constant that every -free graph on vertices with no independent set of size larger than has at most edges?
In our paper, we show that the answers to the questions are: yes, yes, and no.
Bollobás and Erdős drew attention to the interesting transition point of exactly edges. Thus far, the best result for this regime was a lower bound on the independence number of by Sudakov. The proof relies on a powerful probabilistic technique known as dependent random choice.
By introducing a new twist on the dependent random choice technique, we substantially improve this lower bound on the independence number at the critical point.
By modifying the construction of Bollobás and Erdős we obtain the following almost-matching lower bound at the critical point.
We summarize the results in the critical window in the following theorem. For a graph and positive integers and , the Ramsey-Turán number is the maximum number of edges a graph on vertices with independence number less than can have without containing as a subgraph. All of the bounds, except for the first result in the first part, which is due to Sudakov, are new. We write to indicate that as .
1. If , then ;
while if , then .
2. If , then ;
while if , then .
3. If , we have