# 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. Canonical: https://closedform.nishachay.tech/e/openai-math-2026-171/ Last updated: 2026-10-14 **Two-coloring the links among a constant times 2ⁿ points always gives a one-color n-dimensional cube, the paper claims.** **Trust:** Claimed, not checked · **Papers:** 1 · **First paper:** September 23, 2026 · **Field:** Combinatorics · **Entry:** 171 *Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error. 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. ## At a glance - **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 cube[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 3[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ⁿ⁻¹ − 1[3]. In 1975 Burr and Erdős asked a sharper question. Is R(Qₙ) at most a fixed constant times 2ⁿ, for every n[4,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 allows[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 theorem[7]. Lee proved the same for a broader sparseness class in 2017[8]. Neither settles the cube, because each corner of Qₙ has n links, and n grows[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 m[10]. Conlon, Fox and Sudakov got 2^(2n+6), which is 64m²[11]. Lee's work gives about m² plus n²m for large n[12]. Tikhomirov then pushed the power of m below 2[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 n[1]. That answers the Burr–Erdős question positively[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ⁿ approaches[15]. Earlier results for a cube against a fixed clique do not imply this one[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ⁿ points[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 discrepancy[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](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf) - September 23, 2026 ## Quoted lines from the paper (18) [1] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > There is an absolute constant $C>0$ such that \[ R(Q_n)\le C2^n \qquad\text{for every integer }n\ge0. \] [2] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > Each red component is too small for $Q_n$, while a blue copy would need $2^{n-1}$ vertices in each block. [3] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > The standard lower-bound coloring with two blocks gives $R(Q_n)\ge3\cdot2^{n-1}-1$. [4] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > In their 1975 paper, Burr and Erd\H{o}s 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. [5] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > Burr and Erd\H{o}s raised the cube question separately in Section 7, asking whether the cubes form an $L$-set. [6] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > Thus cubes reach the logarithmic order of edges per vertex that this necessary condition still permits. [7] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > 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. [8] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > Lee later proved the corresponding assertion for every fixed degeneracy, resolving the bounded-degeneracy form of the Burr--Erd\H{o}s conjecture. [9] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > 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. [10] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > This moved the cube problem from a growing exponent in $m$ to a fixed exponent. [11] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > 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}$. [12] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > 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$. [13] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > The present theorem reaches a constant multiple of $m$. [14] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > Theorem … resolves that question positively. [15] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > 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. [16] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > These conclusions for a fixed clique do not imply the diagonal cube theorem, where the target in both colors grows with $n$. [17] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > 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$. [18] From [The hypercube Ramsey number has linear order](https://github.com/openai/math/blob/main/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf): > The present proof uses the absence of a cube in both colors of a counterexample to derive discrepancy. ## Other sources - [S. A. Burr and P. Erdős, “On the magnitude of generalized Ramsey numbers for graphs”, in Infinite and Finite Sets, Vol. I, Colloquia Mathematica Societatis János Bolyai 10, North-Holland (1975), 215–240](https://www.renyi.hu/~p_erdos/1975-26.pdf) - [V. Chvátal, V. Rödl, E. Szemerédi and W. T. Trotter, Jr., “The Ramsey number of a graph with bounded maximum degree”, Journal of Combinatorial Theory, Series B 34(3) (1983), 239–243](https://doi.org/10.1016/0095-8956(83)90037-0) - [L. Shi, “Cube Ramsey numbers are polynomial”, Random Structures & Algorithms 19(2) (2001), 99–101](https://doi.org/10.1002/rsa.1021) - [D. Conlon, J. Fox and B. Sudakov, “Short proofs of some extremal results II”, Journal of Combinatorial Theory, Series B 121 (2016), 173–196](https://doi.org/10.1016/j.jctb.2016.03.005) - [C. Lee, “Ramsey numbers of degenerate graphs”, Annals of Mathematics 185(3) (2017), 791–829](https://doi.org/10.4007/annals.2017.185.3.2) - [K. Tikhomirov, “A remark on the Ramsey number of the hypercube”, European Journal of Combinatorics 120 (2024), 103954](https://doi.org/10.1016/j.ejc.2024.103954) - [D. Conlon, J. Fox, C. Lee and B. Sudakov, “Ramsey numbers of cubes versus cliques”, Combinatorica 36 (2016), 37–70](https://doi.org/10.1007/s00493-014-3010-x) - [openai/math release notes (2026): model provenance and review status](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model” ## Related - [The Erdős–Gallai cycle-decomposition conjecture](https://closedform.nishachay.tech/e/openai-math-2026-181/) - Combinatorics - [Superexponential van der Waerden numbers](https://closedform.nishachay.tech/e/openai-math-2026-160/) - Combinatorics - [Cycle–clique Ramsey numbers](https://closedform.nishachay.tech/e/openai-math-2026-189/) - Combinatorics - [Classification of finite Euclidean Ramsey configurations](https://closedform.nishachay.tech/e/openai-math-2026-172/) - Combinatorics - [Counterexamples to Ryser’s covering conjecture](https://closedform.nishachay.tech/e/openai-math-2026-162/) - Combinatorics - [Combinatorics](https://closedform.nishachay.tech/science/mathematics/combinatorics/) - Field · 37 results - [Erdős problems](https://closedform.nishachay.tech/topic/erdos-problems/) - Topic · 13 results - [Named conjectures](https://closedform.nishachay.tech/topic/named-conjectures/) - Topic · 85 results - [Ramsey theory](https://closedform.nishachay.tech/topic/ramsey-theory/) - Topic · 5 results - [Graph theory](https://closedform.nishachay.tech/topic/graph-theory/) - Topic · 40 results - [Open since the 1970s](https://closedform.nishachay.tech/open-since/1970s/) - Era · 63 results - [Claimed, not yet checked](https://closedform.nishachay.tech/trust/claimed/) - Trust · 130 results - [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20171%5D%20)