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). Erdos and Sós [12] asked if RT for some constant c. We answer this question by proving the stronger RT. It is known that RT for c>1, so one can say that K₅ has a Ramsey-Turán phase transition at cnlogn. We extend this result to several other K_s's and functions f(n), determining many more phase transitions. We formulate several open problems, in particular, whether variants of the Bollobás-Erdos 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 K_s-free graphs with small independence number are sparse: on n vertices have o(n²) edges.