TY - JOUR

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

AU - Balogh, József

AU - Lenz, John

N1 - Funding Information:
∗This material is based upon work supported by NSF CAREER Grant DMS-0745185, UIUC Campus Research Board Grants 11067, 09072 and 08086, and OTKA Grant K76099. ∗∗ Work supported by 2010 REGS Program of the University of Illinois and the Na-tional Science Foundation through a fellowship funded by the grant DMS 0838434 “EMSW21MCTP: Research Experience for Graduate Students”. Received November 11, 2010 and in revised form July 2, 2011

PY - 2013/3

Y1 - 2013/3

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

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

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

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

U2 - 10.1007/s11856-012-0076-2

DO - 10.1007/s11856-012-0076-2

M3 - Article

AN - SCOPUS:84876909925

VL - 194

SP - 45

EP - 68

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

SN - 0021-2172

IS - 1

ER -