Phase transitions in the Ramsey-Turán theory

Abstract

Let $f(n)$ be a function and $L$ be a graph. Denote by $RT(n,L,f(n))$ the maximum number of edges of an $L$-free graph on $n$ vertices with independence number less than $f(n)$. Erd\H os and Sós asked if $RT\left(n,K_5,c\sqrt{n}\right)=o(n^2)$ for some constant $c$. We answer this question by proving the stronger $RT\left(n,K_5,o\left(\sqrt{n\log n}\right)\right)=o(n^2)$. It is known that $RT\left(n,K_5,c\sqrt{n\log n}\right)=n^2/4+o(n^2)$ for $c>1$, so one can say that $K_5$ has a Ramsey-Turán phase transition at $c\sqrt{n\log n}$. We extend this result to several other $K_s$'s and functions $f(n)$, determining many more phase transitions. We shall formulate several open problems, in particular, whether variants of the Bollobás-Erd\H os graph exist to give good lower bounds on $RT\left(n,K_s,f(n)\right)$ for various pairs of $s$ and $f(n)$. Among others, we use Szemerédi's Regularity Lemma and the Hypergraph Dependent Random Choice Lemma. We also present a short proof of the fact that $K_s$-free graphs with small independence number are sparse.

21 pages