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 {\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.

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 {\delta} on {\epsilon} (a weaker version of regularity was used then). A natural question is: what is the correct dependence between {\delta} and {\epsilon}? Our regularity-free proof of this result significantly improves the dependencies of the parameters. We show that there is a linear dependence between {\delta} and {\epsilon}, which is tight up to a constant factor.

For the lower bound to the {K_4} Ramsey-Turán problem, we modify the construction of Bollobás and Erdős to slightly boost the edge density to just over {n^2/8}. We can answer the following previously open questions about the critical window.

  1. (Bollobás and Erdős 1976) Is it true that for each {\eta>0} there is an {\epsilon>0} such that for each {n} sufficiently large there is a graph with {n} vertices, independence number at most {\eta n}, and at least {(1/8+\epsilon)n^2} edges?
  2. (Bollobás and Erdős 1976) Is it true that for every {n}, there is a {K_4}-free graph with {n} vertices, independence number {o(n)}, and at least {n^2/8} edges?
  3. (Erdős, Hajnal, Simonovits, Sós and Szemerédi 1993) Is it true for some constant {c>0} that every {K_4}-free graph on {n} vertices with no independent set of size larger than {n/\log n} has at most {(1/8 - c) n^2} 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 {n^2/8} edges. Thus far, the best result for this regime was a lower bound on the independence number of {n e^{-O(\sqrt{\log n})}} 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.

Theorem 3 There is an absolute positive constant {c} such that every {n}-vertex graph with at least {n^2/8} edges contains a copy of {K_4} or an independent set of size greater than {c n \cdot \frac{\log \log n}{\log n}}.

By modifying the construction of Bollobás and Erdős we obtain the following almost-matching lower bound at the {n^2/8} critical point.

Theorem 4 There is an absolute positive constant {c'} such that for each positive integer {n}, there is an {n}-vertex {K_4}-free graph with at least {\frac{n^2}{8}} edges and independence number at most {c' n \cdot \frac{(\log \log n)^{3/2}}{(\log n)^{1/2}}}.

We summarize the results in the critical window in the following theorem. For a graph {H} and positive integers {n} and {m}, the Ramsey-Turán number {{\bf RT}(n,H,m)} is the maximum number of edges a graph {G} on {n} vertices with independence number less than {m} can have without containing {H} 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 {f(n) \ll g(n)} to indicate that {f(n)/g(n) \rightarrow 0} as {n \rightarrow \infty}.

Theorem 5 We have the following estimates. Here {c} and {c'} are absolute constants.

1. If {m = e^{-\omega\left((\log n)^{1/2}\right)}n}, then {{\bf RT}(n,K_4,m) = o(n^2)};

while if {m=e^{-o\left((\log n / \log \log n)^{1/2}\right)}n}, then {{\bf RT}(n,K_4,m) \geq \left(1/8-o(1)\right)n^2}.

2. If {m = c n \cdot \frac{\log \log n}{\log n}}, then {{\bf RT}(n,K_4,m) \leq n^2/8};

while if {m=c' n \cdot \frac{(\log \log n)^{3/2}}{(\log n)^{1/2}}}, then {{\bf RT}(n,K_4,m) \geq n^2/8}.

3. If {\frac{(\log \log n)^{3/2}}{(\log n)^{1/2}}\cdot n \ll m \ll n}, we have

\displaystyle \frac{n^2}{8}+\left(\frac{1}{2}-o(1)\right)m n \leq {\bf RT}(n,K_4,m)\leq \frac{n^2}{8}+\frac{3}{2}mn.