Improved bounds on the multicolor Ramsey numbers of paths and even cycles
Abstract
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 $(k1+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. These insights may be of independent interest.
 Publication:

arXiv eprints
 Pub Date:
 January 2018
 arXiv:
 arXiv:1801.04128
 Bibcode:
 2018arXiv180104128K
 Keywords:

 Mathematics  Combinatorics