## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 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)

## On the Ramsey-Turan numbers of graphs and hypergraphs

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.

Information for students and suggested topics for student talks