Constructions for Nearly Diagonal Book Ramsey Numbers

arXiv:2610.36522 · math.CO · Submitted 2026-10-27 · Read on arXiv

math.CO

Submitted: 2026-10-27

Updated: 2026-10-27

Comments: 24 pages, 1 figure

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

The gist: 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.

Abstract

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) at most 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.

Related papers