A monochromatic hypercube in a network only a constant times larger

← All digests

Family 171 · Combinatorics
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Draw every possible connection among a large collection of points, and color each connection red or blue. How many points guarantee a one-color copy of an $n$-dimensional cube?

The cube itself has $2^n$ vertices. The question is whether a host network only a fixed constant times larger always suffices, with the same constant for every dimension. Each cube vertex has $n$ neighbors, so the required pattern becomes more demanding as the dimension grows. A result for graphs whose degrees stay bounded does not answer this question.

The manuscript claims that an absolute constant does suffice. In the language of Ramsey theory, the Ramsey number of the hypercube has linear order in its number of vertices. This resolves the cube question raised by Burr and Erdős in 1975, according to the manuscript.

2. Background and essential definitions

The binary cube graph $Q_n$ has vertex set

$$\{0,1\}^n.$$

Two binary strings are adjacent when they differ in exactly one coordinate. Thus $Q_1$ is a single edge, $Q_2$ is a square, and $Q_3$ is the familiar graph of a solid cube. In general it has $2^n$ vertices and $n2^{n-1}$ edges for $n\geq1$.

For a finite graph $H$, its two-color Ramsey number $R(H)$ is the least integer $M$ such that every red-blue coloring of the edges of the complete graph $K_M$ contains a monochromatic copy of $H$. All edges required by the copy must have one color. Additional edges among its vertices are allowed and may have either color. The copy need not be induced.

The cube is bipartite. Separate its strings according to whether their coordinate sum is even or odd. Every edge crosses between the two classes, each of size $2^{n-1}$. This parity split is a useful structural feature because an embedding can first place one class and then find compatible places for the other.

“Linear order” means that positive constants bound the ratio $R(Q_n)/2^n$ above and below independently of $n$. It is often written $R(Q_n)=\Theta(2^n)$. It does not specify a limiting ratio or a numerical best constant.

3. Development history and previous partial results

Burr and Erdős asked when an entire family of graphs has one common linear Ramsey bound. They considered several sparsity conditions and separately posed the hypercube question. The common constant is essential: an individual finite graph always has some finite Ramsey number.

In 1983, Chvátal, Rödl, Szemerédi and Trotter proved linear bounds for graphs of any fixed maximum degree. The constant could depend on that degree. Much later, Lee obtained linear bounds for each fixed degeneracy. A graph is $d$-degenerate if every nonempty subgraph has a vertex with at most $d$ neighbors. This allows some vertices to have large degree while still imposing global sparsity.

Neither theorem gives a common linear constant for cubes: both their maximum degree and their degeneracy equal $n$, which grows. The cube has about a logarithmic number of edges per vertex relative to its order. It therefore probes a substantially denser regime than fixed-degree examples.

A separate sequence of estimates addressed cubes directly. Shi’s work established a polynomial bound in the cube’s order. Subsequent results approached a quadratic bound: Fox and Sudakov obtained $n2^{2n+5}$, Conlon, Fox and Sudakov obtained $2^{2n+6}$, and Lee obtained $2^{2n}+n^2 2^n$ for sufficiently large $n$.

Tikhomirov then improved the exponent below two when the size is measured as $m=2^n$. His bound has the form $2^{2n-cn+1}+2$ for an absolute $c>0$. The new manuscript claims the next endpoint: a constant multiple of $m$ itself.

There was also strong progress for a cube in one color versus a fixed clique in the other. Those results do not settle the present problem, because here both target graphs grow with $n$. The manuscript draws on their way of dividing a cube into coordinated smaller cubes.

4. What the new manuscripts claim

The single manuscript states that there exists an absolute constant $C>0$ such that

$$R(Q_n)\leq C2^n \qquad\text{for every integer }n\geq0.$$

“Absolute” means that $C$ is independent of dimension. This is the new upper-bound claim.

A standard coloring gives the complementary lower bound

$$R(Q_n)\geq3\cdot2^{n-1}-1 \qquad(n\geq1).$$

For $n\geq2$, take two blocks of sizes $2^n-1$ and $2^{n-1}-1$, color edges within each block red, and edges between blocks blue. Neither red component is large enough for a cube. A blue cube would need $2^{n-1}$ vertices in each block, exceeding the smaller block’s size. This construction explains why the upper bound cannot have a constant arbitrarily close to one.

The paper also records consequences for subgraphs of cubes. If $H$ is a subgraph of $Q_d$ and

$$2^d\leq A|V(H)|,$$

then $R(H)\leq CA|V(H)|$. The condition says that $H$ occupies at least a fixed fraction of the ambient cube’s vertices.

For a spanning subgraph $F$ of $Q_d$, the same absolute constant works for every Cartesian power $F^{\square k}$. Its vertices are $k$-tuples of vertices of $F$; an edge changes one entry along an edge of $F$. Concatenating the binary coordinates embeds the product in $Q_{dk}$, giving

$$R(F^{\square k})\leq C|V(F)|^k.$$

Examples include powers of paths, and of cycles, whose orders are suitable powers of two.

5. Why the advance matters

Importance: 5/5. The claim settles a longstanding central question about sparse Ramsey theory with a constant uniform across all cube dimensions. The improvement is from a power larger than one in the target’s order to a linear bound, rather than a refinement of a leading constant.

Cubes have a distinctive combination of regularity and increasing local complexity. They are highly organized, yet their degrees grow logarithmically with the number of vertices. Showing that every two-color complete graph of comparable size contains such a structure identifies a strong limit on how effectively coloring can hide it.

The uniformity also produces whole new families of linear bounds through Cartesian products. A theorem whose constant depends exponentially on the number of factors would lose this conclusion. The manuscript’s treatment of simultaneous adjacency requirements and distinct vertex assignments is therefore as significant as the final asymptotic notation.

6. The main idea

Common neighbors are only half the problem

Call a cube vertex a role and a host-graph vertex a label. First assign distinct labels to the odd-parity roles. An even role $v$ must then receive a label adjacent, in the selected color, to all already assigned labels of its neighbors. Its candidate set is

$$L_v=\bigcap_{u\sim v}N_G(f(u)),$$

where $f(u)$ is the assigned label, $G$ is the chosen color graph, and $N_G(x)$ denotes the neighbors of $x$.

Nonempty candidate sets do not suffice: several roles might have only the same label available. Hall’s marriage theorem supplies the exact condition for choosing distinct representatives. Every collection of roles must collectively have at least as many available labels as roles.

One device in the manuscript is to assign each role a probability distribution $p_v$ on its candidate set and show that every label has total load at most one:

$$\sum_v p_v(x)\leq1.$$

Since each role distributes one unit of mass, any group of roles then needs enough distinct labels to hold its total mass. This gives Hall’s condition.

Use both colors to find usable pieces

If the desired theorem failed, the paper reduces to a sequence of hosts whose sizes are arbitrarily large multiples of the corresponding cube sizes, but which contain no cube in either color. The absence in both colors imposes restrictions on weighted edge densities.

The proof studies patches: pairs of host sets equipped with sampling distributions. A distribution can focus on a smaller region, but its concentration is controlled. If a patch has sufficient bias toward one color, that surplus can help create large common neighborhoods. If no such usable bias is available, the argument derives stronger balance properties across many possible weighted patches.

The host patches receive smaller subcubes formed by fixing initial binary coordinates. The remaining coordinates describe edges inside a piece, while the fixed coordinates identify edges that must run between pieces. A slight density gain can accumulate across many adjacency requirements and compensate for the loss caused by splitting the host.

Finish without collisions

Some branches produce enough surplus to establish the probability-load bound directly. Others preserve candidate lists through a delayed assignment of selected cube roles. These delayed classes are organized using a linear map on binary strings, so each relevant role is affected in a controlled way when a class is reassigned.

The final construction leaves pairs of candidates and bounds the chance that a collection of them violates Hall’s condition. Throughout, the sampling must preserve the correct distributions while avoiding repeated labels. The strategy thus coordinates three demands: the right edge color, enough common neighbors, and injectivity of the whole embedding.

7. Scope, limitations, and open questions

The theorem determines the order of growth, but supplies no numerical value for the absolute constant. It does not determine whether $R(Q_n)/2^n$ converges, or what its limit would be. Closing that constant-scale uncertainty is a stronger problem.

The copy is a subgraph copy. Requiring all nonedges of the cube to appear in a prescribed way would be an induced Ramsey problem, outside the stated result. Likewise, the theorem concerns two edge colors; additional colors require separate estimates.

The subgraph consequence needs control of the ambient cube’s size. Merely embedding a small graph somewhere in a much larger cube does not give a useful linear constant in that graph’s own order. The Cartesian-power corollary works because the chosen factor spans its cube, preserving the vertex count exactly under products.

Finally, the theorem is an existence statement for every coloring. The headline does not promise an efficient procedure that finds the monochromatic cube or produces an optimized constant for applications.

8. Sources and further reading

The manuscript’s introduction gives the historical bounds, the subgraph and Cartesian-product consequences, and a four-phase guide to the embedding argument. Its common-neighborhood formulation is a useful starting point before the technical sampling estimates.

Primary landmarks include Burr–Erdős’s 1975 questions, the bounded-degree theorem, Lee’s degeneracy theorem, and Tikhomirov’s subquadratic cube bound. Hall’s original paper supplies the matching principle used to turn candidate sets into distinct assignments.

Source manuscripts

• M1. OpenAI, The hypercube Ramsey number has linear order (September 23, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.