Ramsey Numbers for Book Graphs

Prove a tight lower bound on Ramsey numbers for a class of off-diagonal book graphs.

Notability: Moderately interesting

Solved: No

Contributor: William J. Wesley

Field: Combinatorics

On this page:

About the problem Attempts by AI AI prompts Mathematician survey

About the problem

This problem aims to determine the Ramsey numbers $R(B_{n-1}, B_n)$, where $B_n$ denotes a triangular book graph on $n$ vertices. The upper bound $R(B_{n-1}, B_n) \le 4n - 1$ was established in 1978, and was more recently shown to be sharp for an infinite family of $n$ as well as for all $n \le 21$.

Given these results, it seems likely that the upper bound is sharp for all $n$. The goal of this problem is to prove this, by finding an algorithm that, given $n$, produces a graph witnessing $R(B_{n-1}, B_n) > 4n - 2$.

Warm-up: we ask for a value of $n$ where constructions are already known.

Single Challenge: we ask for a value of $n$ for which no construction is known, and which is probably too hard to brute-force.

Full Problem: we ask for a general algorithm for all $n$.

Full write-up

Attempts by AI

We have evaluated the following models on this problem. “Warm-up” refers to an easier variant of the problem with a known solution.

Model

Problem

Solved

Logs

GPT-5.2 Pro

Warm-up

Yes

GPT-5.2 Pro

Single Challenge

GPT-5.2 Pro

Full Problem

Gemini 3 Deep Think

Single Challenge

AI Prompts

Warm-up

Let B_n denote the triangular book graph on n+2 vertices, i.e. with n triangular "pages".

Construct a graph on 98 vertices that does not contain a copy of B_{24} and whose complement does not contain a copy of B_{25}.

R(B_{n-1}, B_n) > 4n - 2

Output this graph as an adjacency string: a binary string that lists whether an edge is present (1) or absent (0) in column major order, zero-indexed. The order the edges should appear in the string is: {0,1}, {0,2}, {1,2}, {0,3}, {1,3}, {2,3}, {0,4}, {1,4}, {2,4}, {3,4}, ... For example, the string 011010 would represent the 4-vertex graph with edges {0,2}, {1,2}, {1,3}.

Single challenge

Let B_n denote the triangular book graph on n+2 vertices, i.e. with n triangular "pages".

Construct a graph on 198 vertices that does not contain a copy of B_{49} and whose complement does not contain a copy of B_{50}.

Output this graph as an adjacency string: a binary string that lists whether an edge is present (1) or absent (0) in column major order, zero-indexed. The order the edges should appear in the string is: {0,1}, {0,2}, {1,2}, {0,3}, {1,3}, {2,3}, {0,4}, {1,4}, {2,4}, {3,4}, ... For example, the string 011010 would represent the 4-vertex graph with edges {0,2}, {1,2}, {1,3}.

Full problem

Let B_n denote the triangular book graph on n+2 vertices, i.e. with n triangular "pages". 

Find an algorithm that takes n as input and produces a graph on 4n - 2 vertices that does not contain a copy of B_{n-1} and whose complement does not contain a copy of B_{n}.

Provide the algorithm as a Python script that takes n as input and outputs the graph as an adjacency string: a binary string that lists whether an edge is present (1) or absent (0) in column major order, zero-indexed. The order the edges should appear in the string is: {0,1}, {0,2}, {1,2}, {0,3}, {1,3}, {2,3}, {0,4}, {1,4}, {2,4}, {3,4}, ... For example, the string 011010 would represent the 4-vertex graph with edges {0,2}, {1,2}, {1,3}.

For n ≤ 100, the algorithm must complete within 10 minutes when run on a typical laptop.

Mathematician survey

The author assessed the problem as follows.

# of mathematicians highly familiar with the problem: 2–4 mathematicians

# of mathematicians who have made a serious attempt to solve the problem: 2–4

Rough guess of how long it would take an expert human to solve the problem: 1–4 weeks

Notability of a solution: moderately interesting

A solution would be published: in a standard specialty journal

Likelihood of a solution generating more interesting math: somewhat likely: an especially innovative solution could, but is hardly guaranteed

Probability that the problem is solvable as stated: 80–95%