Does the $3$-uniform hypergraph Ramsey number satisfy $R_3(n)\geq 2^{2^{cn}}$? (Erdős #564)
Statement
Let $R_3(n)$ be the $3$-uniform hypergraph Ramsey number: the least $m$ such that every $2$-colouring of the edges (triples) of the complete $3$-uniform hypergraph on $m$ vertices contains a monochromatic complete $3$-uniform hypergraph on $n$ vertices. Is there a constant $c>0$ such that $$R_3(n)\geq 2^{2^{cn}}?$$
Acceptance. FULLY RESOLVES: a complete proof that $R_3(n)\geq 2^{2^{cn}}$ for some constant $c>0$ (matching the doubly-exponential upper bound up to the constant in the exponent), or a proof that no such $c$ exists (i.e. $R_3(n)$ is sub-doubly-exponential) — machine-checkable (Lean/Coq) preferred, otherwise a full written proof with the explicit colouring construction. ADVANCES (each independently checkable): (a) improve the lower bound on $R_3(n)$ beyond the best stated in the background (currently $2^{cn^2}$) toward a doubly-exponential form — e.g. $2^{n^{2+\delta}}$ or $2^{2^{c\sqrt n}}$ — with proof and construction; or (b) reduce the $2$-colour gap by improving the upper bound below the best stated in the background (currently $2^{2^{n}}$), with proof. Deliver the proof together with the explicit construction or argument.
Background
A problem of Erdős, Hajnal, and Rado [EHR65], reiterated by Erdős [Er81] and [Er97c]; it is the $r=3$ special case of the general hypergraph tower-Ramsey problem, Erdős #562 (erdosproblems.com/562). Listed as open on erdosproblems.com/564 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory | hypergraphs'). Erdős offered \$500 for a solution. Frontier: Erdős, Hajnal, and Rado [EHR65] proved $$2^{cn^2}<R_3(n)<2^{2^{n}}$$ for some constant $c>0$ — the upper bound is doubly exponential (a tower of height $2$) while the best lower bound is only singly exponential in $n^2$ (a tower of height $1$). Erdős conjectured that the truth is doubly exponential, i.e. $R_3(n)\geq 2^{2^{cn}}$, closing the gap in favour of the upper bound's tower height. Strong supporting evidence comes from more colours: Erdős, Hajnal, Máté, and Rado [EHMR84] proved a doubly-exponential lower bound for the analogous $4$-colour problem, leaving the $2$-colour case as the outstanding gap. This is #37 in the Ramsey Theory section of the Erdős problem collection. Attacker's tool: a new stepping-up / product colouring construction yielding a doubly-exponential $2$-colour lower bound; the relevant hypergraph Ramsey numbers are astronomically large (already $R_3(4)$ is enormous), so this is a purely constructive/asymptotic attack rather than any computational search.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #564 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.