Episode 171, October 2026

Hypercube Ramsey: linear at last?

A preprint claims that every red/blue colouring of the pairs among a constant times 2ⁿ points contains a one-coloured n-dimensional cube

Covers result 171 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.

Play Episode 171: Hypercube Ramsey: linear at last? The four-dimensional cube, sixteen corners and thirty-two edges, drawn in one colour (our drawing).

5:50. English captions available. The video loads from YouTube when you press play.

Chapters

The claim, in plain words

The cube Q_n has the 2ⁿ strings of n zeros and ones as corners, joined when they differ in one place: a square for n = 2, the ordinary cube for n = 3. Colour every pair of points red or blue. The Ramsey number R(H) is the fewest points that guarantee a copy of H in one colour; “the copy is not required to be induced”. A simple two-block colouring gives R(Q_n) ≥ 3·2ⁿ⁻¹ − 1. In 1975 Burr and Erdős asked which families of graphs have Ramsey numbers at most a fixed constant times their number of vertices, and “raised the cube question separately”. Chvátal, Rödl, Szemerédi and Trotter (1983) answered it for bounded degree and Lee (2017) for bounded degeneracy, but these “did not settle the cube question because both the maximum degree and the degeneracy of Q_n equal n”. As the paper recounts, the upper bounds for R(Q_n), in terms of m = 2ⁿ, went from m^{O(log log m)} (Graham, Rödl and Ruciński) to a fixed power (Shi), to about m² (Fox and Sudakov; Conlon, Fox and Sudakov; Lee), and to 2^2n−cn+1 + 2 for an absolute c > 0 (Tikhomirov).

Result 171 is a single OpenAI preprint, The hypercube Ramsey number has linear order (172 pages, dated September 23, 2026). Theorem 1.1: “There is an absolute constant C > 0 such that R(Q_n) ≤ C2ⁿ for every integer n ≥ 0.” With the lower bound, the Ramsey number of the cube is within a constant factor of its number of corners: “This resolves positively the hypercube Ramsey conjecture of Burr and Erdős.” If a graph H fills a fraction 1/A of some cube, then R(H) ≤ CA|V(H)|; and the paper notes that Cartesian powers of paths and cycles on 2^d vertices, such as grids with 2^d points per side, get Ramsey numbers at most C times their size, with one constant for any number of factors.

What it doesn’t claim

“It gives no numerical value for C and does not determine whether R(Q_n)/2ⁿ converges or what its limiting value would be”; the conclusion repeats that “this existence argument does not provide a numerical value for C”. The ratio is at least about 1.5 by the lower bound; how far above that it can go is not known. The statement is for two colours and the same cube in both, and the proof is by contradiction, with no algorithm or explicit embedding.

Where it stands

Posted as a preprint: OpenAI, 172 pages, dated September 23, 2026
Peer reviewed: Not yet
Checked in Lean: No: the main theorem is not formalized

Last checked October 19, 2026. The preprint has not been revised since it was added to the repository in its initial commit on October 6, 2026. The main theorem is not formalized in Lean: the catalogue has no Lean link for this result, and there is no scope note or comparator. The library does contain one short file (287 lines, not linked from the catalogue) proving crude bounds 2ⁿ ≤ R(Q_n) ≤ 2^2ⁿ⁺¹, the case n = 0, and the paper’s opening reduction to a counterexample sequence; we have not rebuilt it. At 172 pages, with many constants left unspecified, the proof needs careful expert checking. The paper is not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

A counterexample sequence. If R(Q_n)/2ⁿ were unbounded, there would be colourings between two sides of N points, with N/2ⁿ → ∞ at an unknown, possibly very slow, rate, and no one-coloured cube across them (Lemma 2.1).
Candidate lists. The even corners go to one side and the odd corners to the other. Once the odd corners are placed, an even corner can only go to a common neighbour of its n placed neighbours. In a balanced colouring that leaves about N/2ⁿ candidates, barely more than a constant.
Bias is a resource. If each of n restrictions keeps a label with probability ½ + δ, a set of M labels keeps M(½ + δ)ⁿ, a factor (M/N)(1 + 2δ)ⁿ over N/2ⁿ. Sections 4 to 12 show that usable bias or near-purity in either colour would give a cube, so a counterexample must have “deep discrepancy”: densities within about n^−1+0.04 of one half, even for laws concentrated on small sets.
Tiling. The cube is cut into subcubes by fixing initial coordinates, with sizes matched to disjoint patches of the host in one colour, the geometry of earlier cube-versus-clique tilings. The remaining gain, from edge density or from clusters of common neighbours, pays for the smaller pieces and the cube edges that cross between them. With a large gain, the odd corners are placed directly and Hall’s theorem places the even ones.
Small gains. Coordinates get distinct IDs in a binary group, and the syndrome Σ a_kz_k splits the odd corners into classes, so that each even corner has at most one neighbour in each class, an idea from Hamming’s parity-check codes. About log n late classes are relabelled last from reserved pools, each even corner keeps two candidates, and a two-endpoint Hall estimate (Lemma 18.6) fits them all. That contradicts the counterexample.

The numbers in the video

Our check of R(Q₂) = 6 (classical): 72 of the 1,024 colourings of 5 points avoid a one-coloured 4-cycle, the pentagon colouring among them; none of the 32,768 colourings of 6 points do.
Our check of the two-block colouring for n = 3: red cliques on 7 and 3 points, blue between them, with no one-coloured cube.
The upper bounds, as the paper cites them: 8(16n)ⁿ, n·2²ⁿ⁺⁵, 2²ⁿ⁺⁶, 2²ⁿ + n²2ⁿ and 2^2n−cn+1 + 2.
Our random-colouring illustration (not the paper’s method): with n = 10 and 4·2¹⁰ points per side, an even corner had 3.80 candidates on average, and 8 of the 512 had none.
Our syndrome check in 8 dimensions: 8 classes of 16 odd corners, and every even corner has exactly one neighbour in each.
Our Gray-code cycle through the corners of Q₃: 000 001 011 010 110 111 101 100.

Read the source

The hypercube Ramsey number has linear order (PDF), 172 pages.
The supporting Lean file (the main theorem is not formalized).
The collection’s catalog, where this is result 171.

The paper

OpenAI groups related papers into one result; this one has a single paper.

The hypercube Ramsey number has linear order

Transcript

Read the full script

0:00The question

Write down every string of n zeros and ones, and join two strings when they differ in one place. That is the cube Qₙ: a square for n = 2, the ordinary cube for 3. It has 2ⁿ corners, and each corner has n neighbours. Now colour every pair of points red or blue. The Ramsey number R of a graph is the fewest points that guarantee a copy of it all in one colour, extra edges allowed. The square is a four-cycle. In our check, 72 of the 1,024 colourings of 5 points avoid a one-coloured four-cycle, the pentagon and its star among them, but none of the 32,768 colourings of 6 points do. So R of the square is 6. For every cube, one colouring gives a lower bound: two groups, red inside, one a point short of the cube’s size, the other a point short of half that, joined in blue. Neither colour has room for the cube, so R(Qₙ) is at least one and a half times its number of corners, minus one. In 1975, Burr and Erdős asked which families of graphs have Ramsey numbers at most a fixed constant times their number of vertices, and asked separately whether cubes do. Graphs of bounded degree were settled by Chvátal, Rödl, Szemerédi and Trotter in 1983, and bounded degeneracy by Lee in 2017. But a cube’s degree is n, which grows, so their constants can grow with it. Cubes also sit at the edge of what is possible: a counting argument rules out such a bound for families with many more edges per vertex than the log of their size, and the cube has half the base-two log of its size. Measured against the cube’s size m, the upper bounds went from Graham, Rödl and Ruciński’s m to a power growing like log log m, then a fixed power, then about m², from Fox, Conlon and Sudakov and from Lee, and in 2024 Tikhomirov’s m to a fixed power below two.

2:01The claim

Result 171 is a single OpenAI preprint, 172 pages long, dated September 23. Its main theorem: there is an absolute constant C such that R(Qₙ) is at most C times 2ⁿ, for every n. With the old lower bound, the Ramsey number of the cube is within a constant factor of its number of corners, which would answer Burr and Erdős’s question. A similar bound covers any graph that fills a fixed fraction of some cube, and C itself covers, for example, cycles whose length is a power of two, and square grids with a power-of-two number of points per side, in any number of dimensions. Not claimed: the value of C. The paper says its existence argument gives no number, and it does not determine whether R(Qₙ)/2ⁿ has a limit. The truth could be anywhere from one and a half times the number of corners to C times it. It is two colours only, the same cube in both, and copies need not be induced. There is no algorithm and no explicit embedding: the proof is by contradiction.

3:06How the proof goes

Suppose the ratio were unbounded. Then there would be colourings between two sides of N points each, with N/2ⁿ growing without bound, perhaps very slowly, and no one-coloured cube across them. Put the even corners of the cube on one side and the odd corners on the other, so every cube edge crosses. Once the odd corners are placed, an even corner can only go to a common neighbour of its n placed neighbours. In a balanced colouring each neighbour keeps about half the candidates, leaving about N/2ⁿ: barely more than a constant. In our simulation of a random colouring with 4 × 2¹⁰ points per side, an even corner had about 4 candidates on average, and 8 of the 512 had none. So imbalance is a resource: a surplus at each of the n steps compounds, and a nearly one-coloured patch is even better. Case by case, sections 4 to 12 show that any usable bias or purity would give a cube. Since a counterexample has no cube in either colour, it must be balanced almost perfectly, to within about one part in n, even on small pieces. Then the cube is cut into subcubes by fixing its first coordinates, with sizes matched to disjoint pieces of the host, as in earlier work on cubes against cliques. What remains of the bias, or dense clusters of common neighbours, pays for the smaller pieces and the cube edges that cross between them. When that gain is large, the odd corners are placed directly, and Hall’s matching theorem places the even ones. When it is small, a parity-check map, as in Hamming’s codes, splits the odd corners into classes, so that each even corner has at most one neighbour in each class. In our check in 8 dimensions, there are 8 classes of 16 odd corners, and every even corner has exactly one neighbour in each. About log n of the classes are labelled last, leaving each even corner two candidates, and a final Hall estimate fits them all. That contradicts the counterexample.

5:06Where it stands

The paper is a preprint, not peer reviewed, and not revised. Its main theorem is not formalized in Lean: OpenAI’s library has one short file, not linked from the catalogue, with crude bounds and the proof’s opening reduction. At 172 pages, with many constants left unspecified, it needs careful checking. It is not among the papers OSVerify reviewed, and we have seen no expert review. If it holds, the Ramsey number of the n-dimensional cube is within a constant factor of 2ⁿ, answering Burr and Erdős’s question about cubes. The constant is unknown, and so is whether the ratio has a limit.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.