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\).
Progress Update (2026-05-02). Several researchers have elicited AI solutions for values of \(n\) for which no construction was previously known. The first and most comprehenseive set of such results was shared with us by David Turturean. David used a scaffold powered originally by GPT-5.2 Pro and later by GPT-5.4 Pro for the core mathematical work, and used Claude Code powered by Opus 4.6 for coding. These results consist of two additional infinite families based on constructions found in the mathematical literature, and a search program that found constructions for all remaining \(n \le 56\). More details on David’s results can be found here.
We have changed the value of the “single challenge” from 50, which is now resolved, to 100.
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.
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}.
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 398 vertices that does not contain a copy of B_{99} and whose complement does not contain a copy of B_{100}.
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 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}.
Solution format:
* Write a Python script defining a function `solution(n: int) -> str`.
* Do not include any code at the file level. You may include a `main` block for testing, but it will not be executed by the verifier.
* 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.
Number of mathematicians highly familiar with the problem:
2–4 mathematicians
Number 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%