When: Sunday, April 27, 10am
Where: Schreiber 309
Speaker: Tibor Szabo, Berlin
Title: What is Ramsey-equivalent to a clique?
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.
