On the Ramsey-Turán numbers of graphs and hypergraphs

József Balogh, John Lenz

Research output: Contribution to journalArticlepeer-review

Abstract

Let t be an integer, f(n) a function, and H a graph. Define the t-Ramsey-Turán number of H, RTt(n,H, f(n)), to be the maximum number of edges in an n-vertex, H-free graph G with αt(G) ≤ f(n), where αt(G) is the maximum number of vertices in a Kt-free induced subgraph of G. Erdo{double acute}s, Hajnal, Simonovits, Sós and Szemerédi [6] posed several open questions about RTt(n,Ks, o(n)), among them finding the minimum ℓ such that RTt(n,Kt+ℓ, o(n)) = Ω(n2), where it is easy to see that RTt(n,Kt+1, o(n)) = o(n2). In this paper, we answer this question by proving that RTt(n,Kt+2, o(n)) = Ω(n2); our constructions also imply several results on the Ramsey-Turán numbers of hypergraphs.

Original languageEnglish (US)
Pages (from-to)45-68
Number of pages24
JournalIsrael Journal of Mathematics
Volume194
Issue number1
DOIs
StatePublished - Mar 2013

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'On the Ramsey-Turán numbers of graphs and hypergraphs'. Together they form a unique fingerprint.

Cite this