Constructions for Nearly Diagonal Book Ramsey Numbers
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality