Discrete Lunch‎ > ‎

Anita Liebenau on Ramsey equivalence

posted Feb 28, 2015, 11:54 PM by Dirk Oliver Theis
After winter break and traveling, we met on Monday, Feb 23, for Anita Liebenau's talk on which graphs are Ramsey equivalent to cliques. Here's her abstract.
The concept of Ramsey-equivalence was introduced only recently, in 2010, by Szabo, Zumstein and Zürcher. A surprising fact is that the only connected graph that is Ramsey-equivalent to the clique K_k on k vertices is K_k itself. That is, removing a single edge from K_k, or adding a single pendant edge to it, completely changes the Ramsey behavior. In this talk, we will define Ramsey-equivalence of two graphs and see some recent results on Ramsey-equivalence. There are lots of open problems in this area, and I will mention some of them.