The hypercube Ramsey conjecture

1 · The essentials

Imagine a collection of points with every pair joined by a line, and color each line either red or blue. The question is whether some of these points and lines must contain the pattern of a cube, with all the lines belonging to that pattern the same color. Here cubes can have any number of dimensions, and an $n$ -dimensional cube has $2^{n}$ corners. The manuscript claims that a fixed constant times that many points always suffices, regardless of how the colors are chosen. The same constant works for every dimension. The manuscript describes this as a positive resolution of the hypercube Ramsey conjecture of Burr and Erdős. This result has not been formalized in Lean or formally verified.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, picture people at a gathering, with every pair assigned either a red or a blue ribbon. The claim says that a gathering sufficiently large in proportion to a cube’s number of corners must contain people whose ribbons trace that cube in one color; ribbons not used in the pattern do not matter.

Why it matters

The claim gives a uniform answer across all dimensions: the required number of vertices is bounded by a constant times the cube’s own number of vertices. The repository summary describes the resulting growth rate as $Θ (2^{n})$ , and the manuscript identifies the bound as resolving the Burr–Erdős hypercube Ramsey conjecture.

2 · Going further

The precise problem concerns the two-color Ramsey number of the $n$ -dimensional binary cube, denoted here by $r (Q_{n})$ . This is the smallest size of a complete graph for which every red-blue coloring of its edges contains a monochromatic copy of $Q_{n}$ . The main manuscript claims $r (Q_{n}) \leq C 2^{n}$ , where $C$ is an absolute constant, independent of $n$ . The repository summary states the overall conclusion as $r (Q_{n}) = Θ (2^{n})$ : the Ramsey number has linear order in the cube’s number of vertices.

The context supplied is the hypercube Ramsey conjecture of Burr and Erdős, which the manuscript says this bound resolves positively. The abstract states the bound but does not describe the argument, so no construction, intermediate estimate, or proof strategy can be reported from the supplied material. Only one manuscript is provided; there are no supplied companion manuscripts whose relationship can be explained.

Useful notions

Graphs: vertices and edges
Complete graphs
Red-blue edge colorings
Binary cubes and dimension
Growth rates up to constant factors

What was known before / what is new

Before

The source identifies the target problem as the hypercube Ramsey conjecture of Burr and Erdős. It supplies no earlier bounds, partial results, or historical timeline.

New

The main manuscript claims an upper bound of $C 2^{n}$ for the two-color Ramsey number of the $n$ -dimensional binary cube, with one absolute constant $C$ . It describes this as a positive resolution of the conjecture; the repository summary expresses the conclusion as $Θ (2^{n})$ .

Limits and assumptions

The claim concerns red-blue edge colorings of complete graphs and monochromatic copies of binary cubes. The constant must be independent of dimension, but the supplied abstract gives no numerical value for it and no argument establishing the bound. The main result is not formalized in Lean and has not been formally verified. The source lists no remaining open questions and gives no claims about other numbers of colors or other target graphs.

Mini glossary

Complete graph: A graph with an edge joining every pair of distinct vertices.
Binary cube: The graph whose vertices are length- $n$ binary strings, with edges joining strings that differ in exactly one position.
Monochromatic copy: A copy of a target graph whose edges all have the same color.
Two-color Ramsey number: The smallest number of vertices in a complete graph that guarantees a monochromatic copy of the target graph under every red-blue edge coloring.
Absolute constant: A fixed constant that does not depend on the cube’s dimension.
Linear order: Growth bounded above and below by positive constant multiples of the quantity being compared, here the cube’s $2^{n}$ vertices.

Keywords : Hypercube · Ramsey number · Edge coloring

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Resolves the Burr–Erdős hypercube Ramsey conjecture: the two-color Ramsey number of the n-dimensional cube is $Θ (2^{n})$ . Thus every red-blue coloring of a complete graph on a universal constant times the cube's number of vertices contains a monochromatic copy of the cube.

To be verified: the proof is written in the manuscript, but no software has checked it and no validation by independent mathematicians is established. It may contain errors.

Manuscripts in this family

★

The hypercube Ramsey number has linear order

23/09/2026

To be verified

We prove that the two-color Ramsey number of the n-dimensional binary cube is at most $C 2^{n}$ , where C is an absolute constant. This resolves positively the hypercube Ramsey conjecture of Burr and Erdős.

PDF GitHub folder