Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 21, 2016, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Alexey Pokrovskiy
Given a pair of graphs G and H, the Ramsey number R(G,H) is the smallest N such that every red-blue coloring of the edges of the complete graph on N vertices contains a red copy of G or a blue copy of H. If a graph G is connected, it is well known that R(G,H) is at least (|G|-1)(c(H)-1) + s(H), where c(H) is the chromatic number of H and s(H) is the size of the smallest color class in a c(H)-coloring of H. A graph G is called H-good if R(G,H) = (|G|-1)(c(H)-1) + s(H). The notion of Ramsey goodness was introduced by Burr and Erdös in 1983 and has been extensively studied since then. We will show that the path P is H-good for any graph H with |P|≥4|H|. For graphs with c(G)≥4, this confirms in a strong form a conjecture of Allen, Brightwell, and Skokan. Some results about Ramsey goodness of cycles will be presented as well. This is joint work with Sudakov.
Automatic MiSe System Software Version 1.4803M | admin login