Phase transitions in Ramsey-Turán theory

József Balogh, Ping Hu, Miklós Simonovits

Research output: Contribution to journalArticle

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 K5 has a Ramsey-Turán phase transition at cnlogn. 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-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 Ks-free graphs with small independence number are sparse: on n vertices have o(n2) edges.

Original languageEnglish (US)
Pages (from-to)148-169
Number of pages22
JournalJournal of Combinatorial Theory. Series B
Volume114
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Phase transitions in Ramsey-Turán theory'. Together they form a unique fingerprint.

  • Cite this