Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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**: OAT S15/S16/S17

**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 K_{k}. A famous theorem of Folkman implies that any graph H which is Ramsey-equivalent to K_{k} must contain K_{k}.

In this talk, we show that the only connected graph which is Ramsey-equivalent to K_{k} is itself. This gives a negative answer to the question of Szabó, Zumstein, and Zürcher on whether K_{k} is Ramsey-equivalent to K_{k}.K_{2}, the graph on k+1 vertices consisting of K_{k} with a pendant edge.

We also address the question of which non-connected graphs are Ramsey-equivalent to K_{k}. Let f(k,t) be the maximum f such that the graph H=K_{k}+fK_{t}, consisting of K_{k} and f disjoint copies of K_{t}, is Ramsey-equivalent to K_{k}. 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ó.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login