## Abstract

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_{5} 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^{2}) edges.

Original language | English (US) |
---|---|

Pages (from-to) | 148-169 |

Number of pages | 22 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 114 |

DOIs | |

State | Published - Sep 1 2015 |

## Keywords

- Dependent random choice
- Independence number
- Ramsey
- Turán

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics