Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 27, 2014, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Anita Liebenau (University of Warwick)
A graph G is Ramsey for H if every two-colouring of the edges of G contains a monochromatic copy of H. Two graphs H and H' are Ramsey-equivalent if every graph G is Ramsey for H if and only if it is Ramsey for H'. We study the problem of determining which graphs are Ramsey-equivalent to the complete graph Kk. A famous theorem of Folkman implies that any graph H which is Ramsey-equivalent to Kk must contain Kk.
In this talk, we show that the only connected graph which is Ramsey-equivalent to Kk is itself. This gives a negative answer to the question of Szabó, Zumstein, and Zürcher on whether Kk is Ramsey-equivalent to Kk.K2, the graph on k+1 vertices consisting of Kk with a pendant edge.
We also address the question of which non-connected graphs are Ramsey-equivalent to Kk. Let f(k,t) be the maximum f such that the graph H=Kk+fKt, consisting of Kk and f disjoint copies of Kt, is Ramsey-equivalent to Kk. Szabó, Zumstein, and Zürcher gave a lower bound on f(k,t). We prove an upper bound on f(k,t) which is roughly within a factor 2 of the lower bound.
Joint work with J. Fox, A. Grinshpun, Y. Person and T. Szabó.
Automatic MiSe System Software Version 1.4803M | admin login