Skip to content

Erdős Problem #181

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, ramsey theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

The \(n\) dimensional hypercube graph \(Q_n\) has the \(2^n\) binary words of length \(n\) as vertices; two words are adjacent if they differ in exactly one coordinate. Its number of edges is \(n2^{n-1}\).

The ordinary two-colour Ramsey number \(R(Q_n)\) is the smallest \(N\) for which every red-blue colouring of the edges of \(K_N\) contains a monochromatic subgraph isomorphic to \(Q_n\). Burr and Erdős conjectured that

\[ R(Q_n)\le C\,2^n \]

with an absolute constant \(C\) independent of \(n\). This is a linear bound in the number of vertices of the cube, not linear in its dimension \(n\).

A small example

The two-dimensional cube \(Q_2\) is a four-cycle. It has four vertices and four edges, unlike \(K_4\), which has six edges. For the three-dimensional cube, each of eight vertices has degree three, giving \(3\cdot8/2=12\) edges. A graph copy need not be induced, so additional edges among its cube vertices do not disqualify it as a monochromatic subgraph.

The immediate upper estimate follows by embedding \(Q_n\) into the complete graph on the same \(2^n\) vertices and applying the ordinary clique Ramsey number: \(R(Q_n)\le R(K_{2^n})\). This grows much faster than the conjectured \(C2^n\).

What is known

The linear conjecture remains OPEN. Konstantin Tikhomirov, A remark on the Ramsey number of the hypercube, 2022, showed an exponential improvement on the trivial clique bound:

\[ R(Q_n)\ll 2^{(2-c)n} \]

for an absolute \(c>0\), with \(c\approx0.03656\) permissible. This is a major reduction in the exponent of two, but \(2^{(2-c)n}\) is still asymptotically far above \(2^n\).

Erdős noted in 1993 that even whether \(R(Q_n)/2^n\) tends to infinity had been uncertain. The maintained #181 continues to classify the desired linear bound OPEN, not proved by Tikhomirov.

GCL's current state

Pinned and maintained classification: OPEN. Original issue: #1450. The primary preprint's qualitative exponent improvement was checked; its embedding and regularity arguments were not independently reconstructed.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded finite fixture constructs \(Q_n\) for \(n=1,2,3,4\) and checks vertex count \(2^n\), degree \(n\), and edge count \(n2^{n-1}\). For \(Q_2\), verify that a candidate monochromatic four-cycle is accepted even when the four chosen vertices have extra edges in the ambient complete graph. Stop before interpreting small Ramsey computations as a proof of the universal constant \(C\).

Sources and claim boundaries

No new linear Ramsey bound, independent full proof audit or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1450 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction