Prove $R(Q_n)\ll 2^n$: is the Ramsey number of the hypercube linear in its vertex count? (Erdős #181)
Statement
Let $Q_n$ be the $n$-dimensional hypercube graph — its vertices are the binary strings of length $n$ (so $2^n$ vertices), two being adjacent when they differ in exactly one coordinate (so $n2^{n-1}$ edges). Let $R(Q_n)$ be its Ramsey number: the least $N$ such that every red/blue colouring of the edges of $K_N$ contains a monochromatic copy of $Q_n$. Prove that $$R(Q_n)\ll 2^n,$$ i.e. $R(Q_n)=O(2^n)$ — linear in the number of vertices of $Q_n$.
Acceptance. FULLY RESOLVES: either (a) a complete proof that $R(Q_n)\ll 2^n$, or (b) a disproof — a proof that $R(Q_n)/2^n\to\infty$. Machine-checkable (Lean/Coq) preferred, otherwise a full written proof with all steps. ADVANCES, each checkable: (a) improve the exponent in the upper bound $R(Q_n)\ll 2^{(2-c)n}$ strictly beyond the best constant stated in the background (Tikhomirov's $c\approx 0.03656$), with a complete proof; (b) a lower bound on $R(Q_n)$ strictly exceeding the trivial $R(Q_n)\ge 2^n$, with an explicit construction. State the improvement in words and prove it strictly beats the background. Deliver the proof file, or the construction plus its verification.
Background
Conjectured by Burr and Erdős [BuEr75]; in [Er93, p.346] Erdős notes that he and Sós studied the growth of $R(Q_n)$ but could not decide whether $R(Q_n)/2^n\to\infty$ or stays bounded. The trivial bound $R(Q_n)\le R(K_{2^n})\le C^{2^n}$ (for some $C>1$) has been improved several times; the current record, due to Tikhomirov [Ti22], is $R(Q_n)\ll 2^{(2-c)n}$ for a small constant $c>0$ (in fact $c\approx 0.03656$ is permissible). Since $2^{(2-c)n}=(2^n)^{2-c}$, the best bound is still essentially the square of the vertex count with a tiny power saving, whereas the conjecture asks for the first power — exponent $1$ in $2^n$. This is #20 in the Ramsey Theory section of the UCSD graphs problem collection. Listed as open on erdosproblems.com/181 (fetched 2026-07-13, status 'open'), tagged graph theory | ramsey theory; no prize is attached. Attacker's tool: this is a proof problem — embedding and dependent-random-choice / random-greedy arguments to drive the upper exponent $2-c$ down toward $1$, or an extremal colouring giving a superlinear lower bound $R(Q_n)/2^n\to\infty$ that would settle it the other way; computational purchase is limited to checking small $n$ and stress-testing candidate colourings.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #181 (T. F. Bloom) | website |
| REF-02 | Ramsey cube — UCSD graphs problem collection (#20, Ramsey Theory) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.