Improved bounds on the multicolor Ramsey numbers of paths and even cycles (Q668084): Difference between revisions

Summary: We study the multicolor Ramsey numbers for paths and even cycles, \(R_k(P_n)\) and \(R_k(C_n)\), which are the smallest integers \(N\) such that every coloring of the complete graph \(K_N\) has a monochromatic copy of \(P_n\) or \(C_n\) respectively. For a long time, \(R_k(P_n)\) has only been known to lie between \((k-1+o(1))n\) and \((k + o(1))n\). A recent breakthrough by Sárközy and later improvement by Davies, Jenssen and Roberts give an upper bound of \((k - \frac{1}{4} + o(1))n\). We improve the upper bound to \((k - \frac{1}{2}+ o(1))n\). Our approach uses structural insights in connected graphs without a large matching.