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.