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
SN - 0024-6093
VL - 44
SP - 1251
EP - 1258
JO - Bulletin of the London Mathematical Society
JF - Bulletin of the London Mathematical Society
IS - 6
ER -