Phase transitions in Ramsey-Turán theory

Let f(n) be a function and H be a graph. Denote by RT(n,H,f(n)) the maximum number of edges of an H-free graph on n vertices with independence number less than f(n). Erdős and Sós [12] asked if RT(n,K5,cn)=o(n2) for some constant c. We answer this question by proving the stronger RT(n,K5,o(nlog⁡n))=o(n2). It is known that RT(n,K5,cnlog⁡n)=n2/4+o(n2) for c>1, so one can say that K5 has a Ramsey-Turán phase transition at cnlog⁡n. We extend this result to several other Ks's and functions f(n), determining many more phase transitions. We formulate several open problems, in particular, whether variants of the Bollobás-Erdős graph exist to give good lower bounds on RT(n,Ks,f(n)) 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 Ks-free graphs with small independence number are sparse: on n vertices have o(n2) edges.