Ramsey goodness of paths

详细信息    查看全文

• 作者：Alexey Pokrovskiy¹ ; ^{dr.alexey.pokrovskiy@gmail.com} ; Benny Sudakov¹ ; ^{benjamin.sudakov@math.ethz.ch}
• 关键词：Ramsey numbers ; Ramsey goodness ; Paths in graphs ; Expanders
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：384-390
• 全文大小：267 K
• 卷排序：122

文摘

Given a pair of graphs G and H  , the Ramsey number R(G,H)R(G,H) is the smallest N   such that every red–blue coloring of the edges of the complete graph KNKN contains a red copy of G or a blue copy of H. If graph G   is connected, it is well known and easy to show that R(G,H)≥(|G|−1)(χ(H)−1)+σ(H)R(G,H)≥(|G|−1)(χ(H)−1)+σ(H), where χ(H)χ(H) is the chromatic number of H and σ   the size of the smallest color class in a χ(H)χ(H)-coloring of H. A graph G is called H  -good if R(G,H)=(|G|−1)(χ(H)−1)+σ(H)R(G,H)=(|G|−1)(χ(H)−1)+σ(H). The notion of Ramsey goodness was introduced by Burr and Erdős in 1983 and has been extensively studied since then. In this short note we prove that n  -vertex path PnPn is H  -good for all n≥4|H|n≥4|H|. This proves in a strong form a conjecture of Allen, Brightwell, and Skokan.