On Ramsey equivalence in graph theory

Anita Liebenau (UNSW)

Abstract

In this talk I will introduce the notion of Ramsey equivalence of two graphs and showcase one or two proofs to illustrate the methods in this field. A graph G is called Ramsey for H if every red/blue-colouring of the edges of G produces a monochromatic copy of H. Two graphs H and H’ are called Ramsey equivalent if every graph G is either Ramsey for both H and H’, or for neither of them. This notion was introduced only in 2010, but arises naturally when studying properties of graphs G that are minimal with respect to being Ramsey for a fixed graph H. Interestingly, the complete graph is not Ramsey equivalent to any other connected graph but itself. My aim is to make this a gentle introduction, so not much previous knowledge on graphs or on Ramsey theory is assumed.