Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 22, 2011, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: József Balogh (University of Illinois at Urbana-Champaign)
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 alphat(G) ≤ f(n), where alphat(G) is the maximum number of vertices in a Kt-free induced subgraph of G. Erdős, Hajnal, Simonovits, Sós, and Szemerédi posed several open questions about RTt(n,Ks,o(n)), among them finding the minimum l such that RTt(n,Kt+l,o(n)) = Ω(n^2). We answer this question by proving that RTt(n,Kt+2,o(n)) = Ω(n^2). From the other side, it is easy to see that RTt(n,Kt+1,o(n)) = o(n^2). Our constructions which show that RTt(n,Kt+2,o(n)) = Ω(n^2) also imply several results on the Ramsey-Turán numbers of hypergraphs.
It is joint work with John Lenz.
Automatic MiSe System Software Version 1.4803M | admin login