The hypercube Ramsey conjecture

Two-coloring the links among a constant times 2ⁿ points always gives a one-color n-dimensional cube, the paper claims.

1 paper September 23, 2026 Explained by AI

The n-dimensional cube graph has 2ⁿ corners, linked when they differ in one coordinate. Color every link between M points red or blue, and ask how large M must be to force a one-color cube. Burr and Erdős asked in 1975 whether M can be a fixed constant times 2ⁿ. This paper claims to prove that it can, which settles the order of growth.

First step

1975

Stefan Burr and Paul Erdős, who posed the cube question

Significance

Major

If the proof holds, it settles a well-known question from 1975, with the best possible order of growth.

Trust

Claimed, not checked

Field

Combinatorics

1 paper

The explanation

Picture an ordinary cube. It has 8 corners and 12 edges. Label each corner by three digits, each 0 or 1, such as 010. Two corners share an edge exactly when their labels differ in one digit. Do the same with n digits and you get the n-dimensional cube graph Qₙ. It has 2ⁿ corners, and each corner has n links.

Now take M points and join every pair. Color each of these links red or blue. The Ramsey number R(Qₙ) is the smallest M that always leaves a one-color copy of the cubeSource 1. The copy may use extra links too; it only needs the cube's own links in one color.

Here is why M must be well above 2ⁿ. Take n = 3, and split 10 points into a block of 7 and a block of 3. Color links inside each block red, and links between blocks blue. A red cube would need 8 points inside one block, and the biggest has 7. A blue cube must put its two halves of 4 corners in opposite blocks, and one block has only 3Source 2. So no one-color cube appears, and R(Q₃) is at least 11. In general this coloring shows R(Qₙ) is at least 3 × 2ⁿ⁻¹ − 1Source 3.

In 1975 Burr and Erdős asked a sharper question. Is R(Qₙ) at most a fixed constant times 2ⁿ, for every nSource 4 Source 5? Cubes are a hard test case. Among families that could have this property, they have about as many links per corner as the known limit allowsSource 6.

Related results came first. Graphs where every vertex has at most a fixed number of links have Ramsey numbers linear in their size, by a 1983 theoremSource 7. Lee proved the same for a broader sparseness class in 2017Source 8. Neither settles the cube, because each corner of Qₙ has n links, and n growsSource 9.

Bounds for the cube itself improved slowly. Write m = 2ⁿ for the number of corners. Shi showed in 2001 that R(Qₙ) is at most a fixed power of mSource 10. Conlon, Fox and Sudakov got 2^(2n+6), which is 64m²Source 11. Lee's work gives about m² plus n²m for large nSource 12. Tikhomirov then pushed the power of m below 2Source 13. For n = 10, the cube has 1,024 corners. The lower bound is 1,535, while Lee's upper bound is 1,150,976.

This paper claims that R(Qₙ) is at most C × 2ⁿ, with one absolute constant C, for every nSource 1. That answers the Burr–Erdős question positivelySource 14. With the lower bound above, the order of growth is settled. The paper gives no number for C, and does not say what R(Qₙ)/2ⁿ approachesSource 15. Earlier results for a cube against a fixed clique do not imply this oneSource 16.

The single hard part is keeping the loss to a constant factor. The proof must handle colorings on only a slowly growing multiple of 2ⁿ pointsSource 17. It assumes a coloring with no one-color cube in either color. From that it derives an imbalance in how the colors are spread, called discrepancySource 18. It then uses that imbalance to place the cube piece by piece.

How sure is this? No Lean formalization is listed for this paper in the openai/math release. So no computer proof checker has checked it. No specialist review has been published.

What it doesn't show. This does not give a numerical value for the constant, or say what R(Qₙ)/2ⁿ tends to.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major only if the proof holds. The constant C is not given as a number. No Lean formalization is listed and no specialist review is published.

Words used

Cube graph Qₙ: The graph whose vertices are all strings of n zeros and ones, linked when they differ in exactly one place.
Ramsey number R(H): The fewest points such that coloring every link among them red or blue always leaves a one-color copy of the graph H.
Monochromatic: All in one color.
Order: The number of vertices of a graph.
Degeneracy: A sparseness measure: a graph is d-degenerate if every part of it has a vertex with at most d links.
Bipartite graph: A graph whose vertices split into two sides, with every link going between the sides.

The original paper

The hypercube Ramsey number has linear order (PDF, opens in a new tab)
September 23, 2026

All quoted lines (18)

There is an absolute constant $C>0$ such that $R(Q_n)\le C2^n \qquad\text{for every integer }n\ge0.$
The hypercube Ramsey number has linear order Back to text
Each red component is too small for $Q_n$ , while a blue copy would need $2^{n-1}$ vertices in each block.
The hypercube Ramsey number has linear order Back to text
The standard lower-bound coloring with two blocks gives $R(Q_n)\ge3\cdot2^{n-1}-1$ .
The hypercube Ramsey number has linear order Back to text
In their 1975 paper, Burr and Erd\Hos called a family of graphs an \emph $L$ -set if one constant bounds the Ramsey number of every member by that constant times its order.
The hypercube Ramsey number has linear order Back to text
Burr and Erd\Hos raised the cube question separately in Section 7, asking whether the cubes form an $L$ -set.
The hypercube Ramsey number has linear order Back to text
Thus cubes reach the logarithmic order of edges per vertex that this necessary condition still permits.
The hypercube Ramsey number has linear order Back to text
Chv\'atal, R\"odl, Szemer\'edi and Trotter proved in 1983 that graphs of any fixed maximum degree have Ramsey number linear in their order, with a constant depending on the degree.
The hypercube Ramsey number has linear order Back to text
Lee later proved the corresponding assertion for every fixed degeneracy, resolving the bounded-degeneracy form of the Burr–Erd\Hos conjecture.
The hypercube Ramsey number has linear order Back to text
These results did not settle the cube question because both the maximum degree and the degeneracy of $Q_n$ equal $n$ : their constants may grow with the dimension.
The hypercube Ramsey number has linear order Back to text
This moved the cube problem from a growing exponent in $m$ to a fixed exponent.
The hypercube Ramsey number has linear order Back to text
For positive integers $n$ , Fox and Sudakov obtained $R(Q_n)\le n2^{2n+5}$ , and Conlon, Fox and Sudakov obtained $R(Q_n)\le2^{2n+6}$ .
The hypercube Ramsey number has linear order Back to text
Lee's Theorem 1.3 and the paragraph following it give $R(Q_n)\le2^{2n}+n^2 2^n$ for all sufficiently large $n$ .
The hypercube Ramsey number has linear order Back to text
The present theorem reaches a constant multiple of $m$ .
The hypercube Ramsey number has linear order Back to text
Theorem … resolves that question positively.
The hypercube Ramsey number has linear order Back to text
It gives no numerical value for $C$ and does not determine whether $R(Q_n)/2^n$ converges or what its limiting value would be.
The hypercube Ramsey number has linear order Back to text
These conclusions for a fixed clique do not imply the diagonal cube theorem, where the target in both colors grows with $n$ .
The hypercube Ramsey number has linear order Back to text
The task in the present diagonal problem is to retain a constant multiplicative loss when the host order is only a slowly diverging multiple of $2^n$ .
The hypercube Ramsey number has linear order Back to text
The present proof uses the absence of a cube in both colors of a counterexample to derive discrepancy.
The hypercube Ramsey number has linear order Back to text

Other sources

181The Erdős–Gallai cycle-decomposition conjectureCombinatorics
160Superexponential van der Waerden numbersCombinatorics
189Cycle–clique Ramsey numbersCombinatorics
172Classification of finite Euclidean Ramsey configurationsCombinatorics
162Counterexamples to Ryser’s covering conjectureCombinatorics

Browse Combinatorics Erdős problems Named conjectures Ramsey theory Graph theory Open since the 1970s Claimed, not yet checked