VibeMathedMath problems solved with AI
Sign in

The Burr-Erdős hypercube Ramsey conjecture

Erdős problem #181 · erdosproblems.com/181

Let QnQ_n be the nn-dimensional hypercube graph, with 2n2^n vertices, and R(H)R(H) the two-colour Ramsey number. Burr and Erdős (1975) called a family of graphs an LL-set if its Ramsey numbers are bounded by a constant times the order, conjectured that bounded-degeneracy families are LL-sets (proved by Lee, 2017), and asked separately whether the cubes form an LL-set. Known bounds: R(Qn)≥3⋅2n−1−1R(Q_n)\ge3\cdot2^{n-1}-1, and upper bounds improved from n22n+5n2^{2n+5} (Fox-Sudakov) and 22n+62^{2n+6} (Conlon-Fox-Sudakov) to 2(2−c)n2^{(2-c)n} (Tikhomirov). Is R(Qn)≤C2nR(Q_n)\le C2^n for an absolute constant CC?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Graph Ramsey theory
Posed by
S. A. Burr and P. Erdős, On the magnitude of generalized Ramsey numbers for graphs, Infinite and Finite Sets (Keszthely, 1973), Colloq. Math. Soc. Janos Bolyai 10, Section 7
Year posed
1975
Years open
51y
Solved
2026-09-23
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Unreviewed
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
40 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: there is an absolute constant CC with R(Qn)≤C2nR(Q_n)\le C2^n for every n≥0n\ge0; with the two-block lower bound 3⋅2n−1−13\cdot2^{n-1}-1 this determines the order of R(Qn)R(Q_n). Consequences: linear Ramsey bounds for subgraphs occupying a fixed fraction of a cube, such as Cartesian powers of paths and other subgraphs of QdQ_d. Not shown: any numerical value of CC, whether R(Qn)/2nR(Q_n)/2^n converges, or the general Burr-Erdős question for other dense families.

What the AI did

Produced by an unreleased internal OpenAI model as part of an OpenAI evaluation on open research problems, published in the openai/math release (pinned commit adc7f12). The release README says the vast majority of results used one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result; this result is not among the README's stated exceptions (the Riemann zeta zero-free region work and the Hodge conjecture for CM abelian varieties). The manuscript is authored as OpenAI with no human author named. No Lean formalization accompanies it, and the README cautions that unformalized results could have issues.

Verification

No independent mathematician has checked this yet. Checked here: abstract, introduction and Theorem 1.1 of the TeX source, read against Burr and Erdős's cube question as the manuscript cites it and against erdosproblems.com Problem 181, which states it as R(Qn)≪2nR(Q_n)\ll2^n and listed it as open when fetched on 7 October 2026. The statement matches. The proof is long (eighteen sections of regime analysis, patch tilings and resampling dynamics) and was not refereed. No Lean formalization; the README cautions that unformalized results could have issues.

Sources

Changelog1 change

Discussion