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

Submission Guidelines

Submission Form

Policies for Authors

Ethics Statement

ISSN: 1944-4184 (e-only)

ISSN: 1944-4176 (print)

Author Index

Coming Soon

Other MSP Journals

This article is available for purchase or by subscription. See below.

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.

PDF Access Denied

We have not been able to recognize your IP address 3.141.244.153 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

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