Constructions for Nearly Diagonal Book Ramsey Numbers
Abstract
The Ramsey number R(G1,G2) is the smallest positive integer n such that for every graph H on n vertices, either H contains a copy of G1 or the complement H̅ contains a copy of G2. Ramsey numbers involving the book graphs Bn, which consist of n triangles sharing a common edge, have attracted recent attention, especially in the ``nearly diagonal'' case R(Bn−1,Bn). Rousseau and Sheehan showed the upper bound R(Bn−1,Bn) ≤ 4n−1 nearly fifty years ago, but no general matching lower bound construction is known. This paper gives several new infinite families of n for which R(Bn−1,Bn) = 4n−1. Some of the main results in this paper were found with assistance from the Station, a multi-agent AI system. These results also appeared in a larger work on autonomous mathematical discovery by the authors and Du in arxiv:2608.23691. This paper is a follow-up to that work: we give complete proofs of the book Ramsey results and discuss their connections to objects in combinatorial design theory.
Related
BibTeX
@misc{chung2026constructions,
title = {{Constructions for Nearly Diagonal Book Ramsey Numbers}},
author = {Stephen Chung and William J. Wesley},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36522},
eprint = {2610.36522},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36522},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Constructions for Nearly Diagonal Book Ramsey Numbers
AU - Stephen Chung
AU - William J. Wesley
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.36522
UR - https://arxiv.org/abs/2610.36522
AB - The Ramsey number R(G_1,G_2) is the smallest positive integer n such that for every graph H on n vertices, either H contains a copy of G_1 or the complement H̅ contains a copy of G_2. Ramsey numbers involving the book graphs B_n, which consist of n triangles sharing a common edge, have attracted recent attention, especially in the ``nearly diagonal'' case R(B_n−1,B_n). Rousseau and Sheehan showed the upper bound R(B_n−1,B_n) ≤ 4n−1 nearly fifty years ago, but no general matching lower bound construction is known. This paper gives several new infinite families of n for which R(B_n−1,B_n) = 4n−1. Some of the main results in this paper were found with assistance from the Station, a multi-agent AI system. These results also appeared in a larger work on autonomous mathematical discovery by the authors and Du in arxiv:2608.23691. This paper is a follow-up to that work: we give complete proofs of the book Ramsey results and discuss their connections to objects in combinatorial design theory.
ER -