Linear-order Ramsey numbers for hypercubes

Source and verification

This article explains family 171 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Cubes as Ramsey targets

The $n$-dimensional cube graph $Q_n$ has vertex set $\{0,1{\}}^n$, with two words adjacent when they differ in exactly one coordinate. It has $2^n$ vertices and degree $n$. For a graph $H$, let $R(H)$ be the least $N$ such that every red-blue edge coloring of $K_N$ contains a monochromatic copy of $H$.

The copy need not be induced. Edges of the host between nonadjacent cube vertices may have either color.

Manuscript claim

There is an absolute constant $C$ such that $R(Q_n)\le C{2}^n$ for every $n\ge 0$. (OpenAI, 2026)

Thus the Ramsey number has linear order in the number of cube vertices. The constant is independent of dimension, even though the maximum degree grows with $n$. A theorem whose constant depends arbitrarily on the maximum degree would not yield this conclusion.

🏷️ A matching order of growth

For $n\ge 1$, split a complete graph into blocks of sizes $2^n-1$ and $2^{n-1}-1$. Color edges within blocks red and edges between blocks blue. A red connected copy of $Q_n$ would have to lie in one block, both of which are too small.

The cube is connected and bipartite, with parity classes of size $2^{n-1}$. A blue copy would embed these two classes into opposite blocks, but the smaller block has only $2^{n-1}-1$ vertices. Hence this coloring contains no monochromatic cube and

$$R(Q_n)\ge 3\cdot 2^{n-1}-1.$$

The claimed upper bound therefore has the correct order. It does not determine the leading constant or prove convergence of $R(Q_n)/2^n$.

🏷️ Common-neighbor lists and Hall’s condition

Divide the cube into even and odd parity vertices. Suppose the odd vertices have already been assigned distinct host vertices in one chosen color graph $G$. For an even vertex $v$, the possible labels form the common-neighbor set

$$L_v=\bigcap _{u\sim v}{N}_G(f(u)).$$

It remains to choose a distinct representative from each $L_v$. Hall’s condition says that this is possible exactly when every collection $S$ of even roles satisfies $|{\bigcup }_{v\in S}{L}_v|\ge |S|$.

A useful sufficient certificate is a probability distribution $p_v$ supported on each list, with load at most one at every host label:

$$\sum _v{p}_v(x)\le 1.$$

Indeed, summing first over roles in $S$ and then over their possible labels gives

$$|S|=\sum _{v\in S}\sum _x{p}_v(x)\le \left|\bigcup _{v\in S}{L}_v\right|.$$

This converts the final embedding problem into control of both common-neighbor sizes and the concentration of their probability laws.

🏷️ Patches and density gains

The manuscript argues from a counterexample sequence with two host sides of size $N$ and $N/2^n\to \infty$, allowing this ratio to diverge arbitrarily slowly. A patch consists of one set on each side together with sampling distributions. The concentration of a law $\mu$ is measured by its width $\log (N{\max }_x\mu (x))$.

The proof repeatedly asks whether patches with certain density gains survive after a small fraction of labels is removed. If such patches are available, they can support embeddings. If they are absent, the coloring must satisfy strong discrepancy bounds: all permitted pairs of sampling laws see edge density close to one half.

These alternatives are used in both colors and in both orientations of the two sides. Knowing only that one color has global density at least one half is not enough to guarantee the needed lists.

The cube is allocated among disjoint patches using subcubes obtained by fixing initial coordinates. This records which cube edges cross between patches. The resulting support loss must be compensated by density gain. As a heuristic, if $n$ independent restrictions each retain a proportion $1/2+\delta$ of an $M$-point set, the expected remaining size is $M(1/2+\delta {)}^n$. Relative to the baseline $N{2}^{-n}$, the factor is

$$\frac{M}{N}(1+2\delta {)}^n.$$

The actual restrictions are dependent. The manuscript’s probability comparisons make this gain calculation usable while accounting for crossing edges, concentration, and injectivity.

🏷️ Small gains and delayed assignments

When the gain is sufficiently large, probability laws on the lists satisfy the load certificate above. The smaller-gain regimes need a separate construction.

A fixed linear map on cube words partitions the odd vertices into classes. A logarithmic number of these classes receive provisional labels, replaced later from reserved host sets. Each even vertex has at most one neighbor in each delayed class. Replacements are performed sequentially while controlling how much each common-neighbor list shrinks.

At the end, every even role retains two candidates. Two candidates per role alone do not imply Hall’s condition: many roles could have the same pair. The source proves joint probability estimates that exclude precisely such Hall-deficient collections.

Throughout, conditioning must include how observations were selected. If a hidden tuple influences the choice of which labels are examined, changing that tuple requires recomputing the selection event in the likelihood. Likewise, sampling labels injectively creates dependence; the proof uses samplers preserving the required marginals while controlling joint probabilities. These comparisons close gaps that a naive independent-label model would leave.

🏷️ Key steps and proof outlines

Why two candidates need a joint estimate

In the small-gain regime, the source finishes with two distinct candidate labels for each even cube vertex. Represent host labels by vertices of an auxiliary multigraph and each cube role by the edge joining its two candidates. Choosing distinct representatives for the roles is equivalent to assigning each edge one of its endpoints without reusing a vertex.

Hall’s condition fails exactly when some edge set has fewer incident vertices than edges. A connected component with this property has at least two more edges than a spanning tree. Thus the obstruction is a connected component containing at least two independent cycles, with parallel edges allowed. A single cycle has equally many edges and vertices and is not itself an obstruction. This reformulation makes the joint probability estimates in “Matching the low-mode lists” usable. (OpenAI, 2026)

Separate geometric dependence from candidate collisions

Fix a patch and one of its disjoint palettes. Let $M$ be its reference size, so there are at most $2M$ available labels, and let $L\le KM/C_n$ be the number of assigned roles. Here $K$ is a fixed constant and $C_n\to \infty$ is the counterexample sequence’s excess host-size parameter.

For $p\le \eta n$ tested roles, form a geometric overlap graph: join two roles when their directly read cell sets overlap or they share a late neighbor. This graph is distinct from the endpoint multigraph. Its rank $j$, meaning vertices minus connected components, measures how many independent overlap relations must be imposed. If $m$ counts its nonisolated vertices, then $m\le 2j$.

The manuscript’s joint comparison constructs deterministic symmetric weights $H_v(x,z)$ for each tested role, before endpoint values are specified. They satisfy

$$\underset{x}{\sup }\sum _z{H}_v(x,z)\le K/M,\underset{x,z}{\max }{H}_v(x,z)\le M^{-2}{e}^{0.01n}.$$

The actual joint probability, with the successful-run event retained, is bounded by their product times a correction of the form

$$e^{O(r)}{K}^p\exp (0.01nm+C^{\prime }pj).$$

Here $r=O(\log n)$ is the number of delayed classes. The comparison first removes dependencies from overlapping resampling histories; it does not assume those histories are disjoint.

A role has only polynomially many geometric partners among $2^{n-o(n)}$ roles. An overlap graph of rank $j$ contains a forest of $j$ required partner relations, whose probability costs $2^{-nj+o(n)j}$ up to polynomial factors. Choose $\eta >0$ with $0.02+C^{\prime }\eta <(\log 2)/2$. Averaging the correction over position tuples then gives a convergent geometric sum: the scarcity of overlap forests pays for the possible dependence.

Two extra identifications pay for a Hall obstruction

First witness connectivity of $p$ row edges by a tree on those rows. Each tree link identifies one endpoint of one row with one endpoint of another. Before further identifications, there are $p+1$ abstract endpoint variables, and the row edges form a tree. Summing a product of kernels by removing leaves uses the row-sum bound once per edge, giving at most

$$2M(K/M{)}^p.$$

For a connected Hall violation, fewer than $p$ endpoint vertices remain. At least two further mergers of endpoint classes are therefore necessary. Retain exactly two such mergers and discard any additional constraints for an upper bound. The quotient has $p-1$ vertices and $p$ edges. On the actual distinct-endpoint support it has no loops. A spanning tree uses $p-2$ edges, leaving two edges to be bounded by the maximum-entry estimate:

$$2M(K/M{)}^{p-2}(M^{-2}{e}^{0.01n}{)}^2\le K^p{M}^{-p-1}{e}^{0.02n}.$$

The two mergers are combinatorial identifications, not independent random events. Different roles may use different kernels; their two uniform bounds suffice.

Sum small and large obstructions separately

After counting connectivity diagrams, position choices, and the two extra mergers, the expected number of small connected Hall violations is bounded by terms of the form

$$e^{O(r)}{p}^4{M}^{-1}{e}^{0.02n}(K/C_n{)}^p,p\ge 3.$$

Sizes one and two cannot violate Hall when endpoints are distinct. Since $M=2^{n-o(n)}$, the factor $M^{-1}{e}^{0.02n}$ decays exponentially. For components of at least $t_0=\lfloor \eta n\rfloor$ edges, it suffices to exclude any connected $t_0$-edge set; its bound is $e^{O(r)}M(K/C_n{)}^{t_0}=o(1)$, however slowly $C_n\to \infty$.

The successful assignment run has probability $1-o(1)$ by the preceding transition estimates. Subtracting the obstruction probabilities leaves positive probability of a full run with Hall matchings in every palette. Their disjointness combines the matchings globally. The early and late odd labels are already injective and all candidates hit their required odd neighbors, so the resulting matching completes the monochromatic cube. The lengthy transition and patch estimates are precisely what supplies the joint kernels and full-run probability used here.

See Also

• Off-diagonal Ramsey numbers treats clique targets and a different entropy-based obstruction to independent sets.
• Strong thin trees also requires one global object to meet many simultaneous constraints, beyond separate average estimates.

🏷️ Manuscripts and verification scope

• The hypercube Ramsey number has linear order — pinned manuscript and companion source.

No family scope page was present at lean/docs/171.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. The hypercube Ramsey number has linear order.