Combinatorics Seminar

When: Sunday, January 3, 10am
Where: Schreiber 309
Speaker: Benny Sudakov, ETH Zurich
Title: Ramsey goodness of paths and cycles

Abstract:

The Ramsey number R(G,H) of two graphs G, H is the smallest N such that every red-blue edge-coloring of the complete graph on N vertices contains a red copy of G or a blue copy of H. Let H be a k-chromatic graph, and let c(H) be the the size of a smallest color class in any k-coloring of H. By taking a disjoint union of k-1 red cliques of size |G|-1 and one red clique of size c(H)-1, it follows that R(G,H) >= (k-1)(|G|-1)+c(H), for a connected graph G. If we have equality in the above bound, a graph G is called H-good.

The notion of Ramsey goodness was introduced by Burr and Erdos in 1983 and has been extensively studied since then. A particular case that attracted a lot of attention is when the graph G is either a path or a cycle. We give a very short proof that the n-vertex path is H-good for all n >= 4|H|. This establishes in a strong form a conjecture of Allen, Brightwell and Skokan. We also prove another conjecture of theirs, asserting that cycles are Ramsey good.

Joint work with Alexey Pokrovskiy.