A path-matching of order $p$ is a vertex disjoint union of nontrivial paths spanning $p$ vertices. Burr and Roberts, and Faudree and Schelp determined the 2-color Ramsey number of path-matchings. In this paper we study the multicolor Ramsey number of path-matchings. Given positive integers $r, p_1, dots, p_r$, define $R^{PM}(p_1, dots, p_r)$ to be the smallest integer $n$ such that in any $r$-coloring of the edges of $K_n$ there exists a path-matching of color $i$ and order at least $p_i$ for some $iin [r]$. Our main result is that for $rgeq 2$ and $p_1geq dotsgeq p_rgeq 2$, if $p_1geq 2r-2$, then [R^{PM}(p_1, dots, p_r)= p_1- (r-1) + sum_{i=2}^{r}leftlceilfrac{p_i}{3}rightrceil.] Perhaps surprisingly, we show that when $p_1<2r-2$, it is possible that $R^{PM}(p_1, dots, p_r)$ is larger than $p_1- (r-1) + sum_{i=2}^{r}leftlceilfrac{p_i}{3}rightrceil$, but in any case we determine the correct value to within a constant (depending on $r$); i.e. [p_1- (r-1) + sum_{i=2}^{r}leftlceilfrac{p_i}{3}rightrceil leq R^{PM}(p_1, dots, p_r)leq leftlceil p_1-frac{r}{3}+sum_{i=2}^rfrac{p_i}{3}rightrceil.] As a corollary we get that in every $r$-coloring of $K_n$ there is a monochromatic path-matching of order at least $3leftlfloorfrac{n}{r+2}rightrfloor$, which is essentially best possible. We also determine $R^{PM}(p_1, dots, p_r)$ in all cases when the number of colors is at most 4. The proof of the main result uses a minimax theorem for path-matchings derived from a result of Las Vergnas (extending Tuttes 1-factor theorem) to show that the value of $R^{PM}(p_1, dots, p_r)$ depends on the block sizes in covering designs (which can be also formulated in terms of monochromatic 1-cores in colored complete graphs). Then we obtain the result above by giving estimates on the block sizes in covering designs in the arbitrary (non-uniform) case.
Download