TY - JOUR

T1 - Some exact Ramsey-Turán numbers

AU - Balogh, József

AU - Lenz, John

N1 - Funding Information:
The first author was supported by NSF CAREER Grant DMS-0745185, UIUC Campus Research Board Grants 11067 and 09072, and OTKA Grant K76099.

PY - 2012/12

Y1 - 2012/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84869450326&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84869450326&partnerID=8YFLogxK

U2 - 10.1112/blms/bds053

DO - 10.1112/blms/bds053

M3 - Article

AN - SCOPUS:84869450326

VL - 44

SP - 1251

EP - 1258

JO - Bulletin of the London Mathematical Society

JF - Bulletin of the London Mathematical Society

SN - 0024-6093

IS - 6

ER -