# Combinatorics Seminar

When: Sunday, April 27, 10am

Where: Schreiber 309

Speaker: Tibor Szabo, Berlin

Title: What is Ramsey-equivalent to a clique?

## Abstract:

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'$. In the talk we discuss the problem of
determining which graphs are Ramsey-equivalent to the complete graph
$K_k$. In particular we prove that the only connected graph which is
Ramsey-equivalent to $K_k$ is itself. This gives a negative answer to
a question of Zumstein, Z\"urcher, and the speaker.

For the proof we determine the smallest possible minimum degree that a
minimal Ramsey graph for $K_k\cdot K_2$ (the graph containing the clique
with a pendant edge) can have.

This represents joint work with Jacob Fox, Andrey Grinshpun, Anita Liebenau,
and Yury Person.

redesigned by barak soreq