An improvement on Łuczak's connected matchings method. Issue 2 (22nd March 2022)

• Record Type: Journal Article
• Authors: Letzter, Shoham
• Is Part Of: Bulletin of the London Mathematical Society. Volume 54:Issue 2(2022)
• Page Start: 609
• Page End: 623
• Publication Date: 2022-03-22
• Subjects: Mathematics -- Periodicals; 510
• DOI: 10.1112/blms.12587
• Languages: English
• ISSNs: 0024-6093

Abstract

Abstract: A connected matching in a graph G $G$ is a matching contained in a connected component of G $G$ . A well‐known method due to Łuczak reduces problems about monochromatic paths and cycles in complete graphs to problems about monochromatic connected matchings in almost complete graphs. We show that these can be further reduced to problems about monochromatic connected matchings in complete graphs. We illustrate the potential of this new reduction by showing how it can be used to determine the 3‐colour Ramsey number of long paths, using a simpler argument than the original one by Gyárfás, Ruszinkó, Sárközy, and Szemerédi (2007).