The pigeonhole principle and multicolor Ramsey numbers

Balaji, Vishal; Lamb, Powers; Lott, Andrew; Patel, Dhruv; Rice, Alex; Singh, Sakshi; Ward, Christine Rose

doi:10.2140/involve.2022.15.857

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

The pigeonhole principle and multicolor Ramsey numbers

Vishal Balaji, Powers Lamb, Andrew Lott, Dhruv Patel, Alex Rice, Sakshi Singh and Christine Rose Ward

Vol. 15 (2022), No. 5, 857–884

DOI: 10.2140/involve.2022.15.857

Abstract

For integers $k, r \geq 2$ , the diagonal Ramsey number $R_{r} (k)$ is the minimum $N \in ℕ$ such that every $r$ -coloring of the edges of a complete graph on $N$ vertices yields 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 \geq 3$ , and we also consider an often-ignored secondary term, which allows us to subtract a positive proportion of the main term that is uniformly bounded below. Asymptotically, we give a self-contained proof that

R_{r} (k) \leq (\frac{3 + e}{2}) \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{1}{2} (3 + e)$ to $\frac{1}{2} (3 + e) - \frac{1}{48} d$ , where $d = 66 - R_{4} (3) \geq 4$ . We also compare our formulas, and previously documented formulas, to some collected numerical data.

Keywords

Ramsey theory, Ramsey number, party problem, pigeonhole principle

Mathematical Subject Classification

Primary: 05C15

Milestones

Received: 7 December 2021

Revised: 17 February 2022

Accepted: 22 February 2022

Published: 3 March 2023

Communicated by Anant Godbole

Authors

Vishal Balaji
Department of Mathematics Millsaps College Jackson, MS United States

Powers Lamb
Department of Mathematics Millsaps College Jackson, MS United States

Andrew Lott
Department of Mathematics Millsaps College Jackson, MS United States

Dhruv Patel
Department of Mathematics Millsaps College Jackson, MS United States

Alex Rice
Department of Mathematics Millsaps College Jackson, MS United States

Sakshi Singh
Department of Mathematics Millsaps College Jackson, MS United States

Christine Rose Ward
Department of Mathematics Millsaps College Jackson, MS United States

Vol. 15, No. 5, 2022