The pigenhole principle and multicolor Ramsey numbers

Abstract

For integers $k,r\ge 2$, the diagonal Ramsey number $R_r(k)$ is the minimum $N\in \mathbb{N}$ such that every $r$-coloring of the edges of a complete graph on $N$ vertices yields on a monochromatic subgraph on $k$ vertices. Here we make a careful effort of extracting explicit upper bounds for $R_r(k)$ from the pigeonhole principle alone. Our main term improves on previously documented explicit bounds for $r\ge 3$, and we also consider an often ignored secondary term, which allows us to subtract a uniformly bounded below positive proportion of the main term. Asymptotically, we give a self-contained proof that $R_r(k)\le \left(\frac{3+e}{2}\right)\frac{(r(k-2))!}{((k-2)!{)}^r}(1+o_{r\to \infty }(1)),$ and we conclude by noting that our methods combine with previous estimates on $R_r(3)$ to improve the constant $\frac{3+e}{2}$ to $\frac{3+e}{2}-\frac{d}{48}$, where $d=66-R_4(3)\ge 4$. We also compare our formulas, and previously documented formulas, to some collected numerical data.

19 pages, typos corrected, to appear in Involve