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
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:
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
- Tikhomirov, arXiv:2208.14568, primary upper-bound improvement.
- Erdős #181, Burr–Erdős conjecture and historical bounds.
- Original GCL issue #1450.
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.