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\).
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 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 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%