Hypergraph Ramsey tower height: does $R_r(n)$ grow like a height-$(r-1)$ tower in $n$? (Erdős #562)
Statement
Let $R_r(n)$ denote the $r$-uniform hypergraph Ramsey number: the least $m$ such that every $2$-colouring of the edges of the complete $r$-uniform hypergraph on $m$ vertices contains a monochromatic complete $r$-uniform hypergraph on $n$ vertices. Prove that, for every fixed $r\geq 3$, $$\log_{r-1}R_r(n)\asymp_r n,$$ where $\log_{r-1}$ is the $(r-1)$-fold iterated logarithm and $\asymp_r$ allows constants depending on $r$. Equivalently: does $R_r(n)$ grow like a tower of exponentials $$2^{2^{\cdot^{\cdot^{n}}}}$$ of height $r-1$?
Acceptance. FULLY RESOLVES: a complete proof that $\log_{r-1}R_r(n)\asymp_r n$ for all $r\geq 3$ — establishing both the height-$(r-1)$ tower lower bound and the matching upper bound — machine-checkable (Lean/Coq) preferred, otherwise a full written proof with all steps. ADVANCES (each independently checkable): (a) resolve the conjecture for a specific $r$ (the $r=3$ case is Erdős #564); (b) improve the lower bound for some fixed $r\geq 3$ to a tower of strictly greater height than currently known, with proof; or (c) improve the upper bound below the best tower stated in the background for some $r$, with proof. Deliver the proof, or the improved bound with its proof.
Background
A problem of Erdős, Hajnal, and Rado [EHR65]; listed as open on erdosproblems.com/562 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory | hypergraphs'). It is the general-$r$ statement whose $r=3$ special case is Erdős #564 (erdosproblems.com/564), for which Erdős offered a cash prize. Context: for ordinary graphs ($r=2$) one has $\log R_2(n)\asymp n$ — the diagonal Ramsey number grows singly exponentially — by Erdős's probabilistic lower bound and the Erdős–Szekeres upper bound. For $r$-uniform hypergraphs the Erdős–Hajnal–Rado stepping-up method produces lower bounds one tower level below the upper bounds: the known bounds sandwich $R_r(n)$ between a tower of exponentials of height $r-2$ and one of height $r-1$ (for $r\geq 3$), and the conjecture is that the truth is the height-$(r-1)$ tower. The gap is already open in the first nontrivial case $r=3$, where it is known that $2^{cn^2}<R_3(n)<2^{2^n}$ (see #564). This problem is #38 in the Ramsey Theory section of the Erdős problem collection. No prize is attached to this generalization itself (the $r=3$ case #564 carries a \$500 prize). Attacker's tool: improved stepping-up / product colouring constructions to raise the lower-bound tower height, matched with Ramsey-type upper-bound arguments; a purely asymptotic combinatorial attack, since the numbers themselves are far beyond any direct computation.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #562 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.