Ramsey Numbers of Odd Cycles Versus Larger Even Wheels

Ryan Alweiss

doi:10.1016/j.disc.2018.01.004

paper

Ramsey Numbers of Odd Cycles Versus Larger Even Wheels

arXiv:1609.03672 · doi:10.1016/j.disc.2018.01.004

Abstract

The generalized Ramsey number $R (G_{1}, G_{2})$ is the smallest positive integer $N$ such that any red-blue coloring of the edges of the complete graph $K_{N}$ either contains a red copy of $G_{1}$ or a blue copy of $G_{2}$ . Let $C_{m}$ denote a cycle of length $m$ and $W_{n}$ denote a wheel with $n + 1$ vertices. In 2014, Zhang, Zhang and Chen determined many of the Ramsey numbers $R (C_{2 k + 1}, W_{n})$ of odd cycles versus larger wheels, leaving open the particular case where $n = 2 j$ is even and $k < j < 3 k /2$ . They conjectured that for these values of $j$ and $k$ , $R (C_{2 k + 1}, W_{2 j}) = 4 j + 1$ . In 2015, Sanhueza-Matamala confirmed this conjecture asymptotically, showing that $R (C_{2 k + 1}, W_{2 j}) \leq 4 j + 334$ . In this paper, we prove the conjecture of Zhang, Zhang and Chen for almost all of the remaining cases. In particular, we prove that $R (C_{2 k + 1}, W_{2 j}) = 4 j + 1$ if $j - k \geq 251$ , $k < j < 3 k /2$ , and $j \geq 212299$ .