Some exact Ramsey-Turán numbers

József Balogh, John Lenz

Research output: Contribution to journalArticlepeer-review

Abstract

Let r be an integer, f(n) be a function, and H be a graph. Introduced by Erds, Hajnal, Sós, and Szemerédi, the r-Ramsey-Turán number of H, RTr(n, H, f(n)), is defined to be the maximum number of edges in an n-vertex, H-free graph G with αr(G)≤f(n), where αr(G) denotes the Kr-independence number of G.In this note, using isoperimetric properties of the high-dimensional unit sphere, we construct graphs providing lower bounds for RTr(n, K r+s, o(n)) for every 2≤s≤r. These constructions are sharp for an infinite family of pairs of r and s. The only previous sharp construction (for such values of r and s) was by Bollobás and Erds for r=s=2.

Original languageEnglish (US)
Pages (from-to)1251-1258
Number of pages8
JournalBulletin of the London Mathematical Society
Volume44
Issue number6
DOIs
StatePublished - Dec 2012

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Some exact Ramsey-Turán numbers'. Together they form a unique fingerprint.

Cite this