Erdős #562 — Erdős–Hajnal–Rado hypergraph Ramsey growth rate: SOLVED at the ≥4-colour endpoint via the stepping-up lemma (2-colour case still open)

Statement

For $r\geq2$ let $R_r(n)$ denote the $r$-uniform hypergraph Ramsey number: the minimal $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. Erdős, Hajnal, and Rado [EHR65] conjectured that, for $r\geq3$, $$\log_{r-1}R_r(n)\asymp_r n,$$ where $\log_{r-1}$ is the $(r-1)$-fold iterated logarithm — i.e. that $R_r(n)$ grows exactly like a tower of exponentials of height $r-1$ with $n$ at the top: $R_r(n)\approx 2^{2^{\cdots^{cn}}}$. (erdosproblems.com/562, direct fetch 2026-07-02.) This is stated as OPEN for the standard $2$-colour case, and is a generalisation of erdos/564, the $r=3$ special case, which carries Erdős's own $\$500$ prize.

What this page documents is the sub-case of the exact same growth law that IS a proved theorem: if the number of colours $q$ is allowed to be $\geq4$ instead of $2$, then $$\log_{r-1}R_r(n;q)\asymp_{r,q} n\qquad\text{for every }r\geq3,\ q\geq4,$$ is fully solved — both the matching upper bound (Erdős–Rado 1952, valid for any fixed $q$) and the matching lower bound (Erdős–Hajnal, unpublished, written up in Graham–Rothschild–Spencer's *Ramsey Theory*, building on the stepping-up lemma of Erdős–Hajnal–Rado [EHR65] and the doubly-exponential $q=4$, $r=3$ base case of Erdős–Hajnal–Máté–Rado [EHMR84]) are theorems. The famous, still-open gap is specifically the $q=2$ (and, more weakly, $q=3$) case — i.e. exactly the case erdosproblems.com lists as #562/#564.

Facts

- The $2$-colour state of the art (still the state of the art after 60+ years): for $r=3$, $2^{cn^2}<R_3(n)<2^{2^{c'n}}$ (Erdős–Hajnal–Rado [EHR65], as quoted verbatim on erdosproblems.com/564 and confirmed in the Tower Gaps paper). The lower bound is only singly exponential in its own exponent ($n^2$ inside one $2^{(\cdot)}$), while the upper bound is doubly exponential — a full tower-height gap of one level. The general-$r$ picture is the same shape: lower bound $R_r(n)\geq T_{r-2}(cn^2)$ (stacking the $r=3$ base via the stepping-up lemma) versus upper bound $R_r(n)\leq T_{r-1}(O(n))$ (Erdős–Rado 1952), where $T_1(x)=x,\,T_{i+1}(x)=2^{T_i(x)}$ — i.e. the upper bound already sits at the conjectured tower height $r-1$ for every $r$ and every fixed $q$, and the entire open problem is purely about catching the lower bound up by exactly one tower level. - The $r=2$ (plain graph) instance of this same law is the fully-solved anchor. Excluded from #562's own statement ($r\geq3$) but structurally the base case: $\log_1 R_2(n)=\log R(n,n)\asymp n$ is a classical theorem — $R(n,n)>2^{n/2}$ (Erdős's founding 1947 probabilistic-deletion argument, Bull. Amer. Math. Soc. 53 (1947), 292–294) and $R(n,n)<4^n$ (Erdős–Szekeres 1935, pigeonhole/recursive counting). Both bounds are single towers of height $1$ with a linear exponent — precisely what #562's law predicts at $r=2$. - The $q\geq4$-colour case is a complete theorem, for every $r\geq3$. The Tower Gaps paper states it exactly for $r=3$: "if we allow four colours instead of two, Erdős and Hajnal … showed … there is a $c>0$ such that $r_3(t;4)\geq2^{2^{ct}}$" — doubly exponential, matching the (colour-independent) Erdős–Rado upper bound $2^{2^{c't}}$ exactly. Iterating the stepping-up lemma (see Solution) from this doubly-exponential $r=3,q=4$ base then gives $R_r(n;4)\geq T_{r-1}(cn)$ for every $r\geq3$, again matching the Erdős–Rado upper bound $T_{r-1}(O(n))$ tower-for-tower. So $\log_{r-1}R_r(n;4)\asymp_r n$ — the full statement of #562, verbatim — is a proved theorem once $q\geq4$. - $q=3$ is a genuine intermediate case, neither fully open nor fully solved. Conlon–Fox–Sudakov (2010, JAMS, arXiv:0808.3760) proved $r_3(n;3)\geq2^{n^{c\log n}}$ — super-exponential, a large improvement on the earlier $2^{cn^2}$-type bound, but still short of the doubly-exponential target ($n^{c\log n}$ grows faster than any polynomial but the exponent tower is still only "1.something" levels deep, not a clean $T_2$). - Why $q\geq4$ specifically, not $q=2,3$: the stepping-up lemma's *base step* — lifting a graph ($r=2$) lower bound to a $3$-uniform one — needs enough colours to encode which of several possible "local configurations" a stepped-up hyperedge falls into; with only $2$ or $3$ colours the encoding degenerates and the construction cannot certify a full extra exponential of savings. Once $r\geq3$, however, the *later* steps of the lemma (lifting $r$-uniform to $(r+1)$-uniform) work for any $q\geq2$ — this is exactly why $R_3(n;4)\geq2^{2^{cn}}$ (needs the 4-colour trick once, at the $2\to3$ step) propagates for free, with only $2$ colours, all the way up to every $r\geq4$ once the $r=3$ base is in hand. This localises the *entire* $60$-year-old $2$-colour gap to a single missing base case. - Formal reduction, already documented in this wiki (erdos/564.md): a positive resolution of #564 (proving $R_3(n)\geq2^{2^{cn}}$ with just $2$ colours) would, via the same stepping-up lemma, immediately settle #562 for all $r\geq4$ as well — the $r=3$, $q=2$ case is "the crucial case" (Mubayi–Suk survey language, cited in erdos/564.md). - Live evidence the $q=2$ conjecture could be false, not just hard: Conlon–Fox–Rödl's "hedgehog" hypergraphs (arXiv:1511.00563, cited in erdos/564.md) show a $3$-uniform hypergraph family whose $2$-colour Ramsey number is *polynomial* while its $4$-colour Ramsey number is *exponential* — a stark counter-example to the heuristic "growth rate shouldn't depend qualitatively on colour count," which is precisely the heuristic underlying the belief that the $q=4$ doubly-exponential result should transfer down to $q=2$.

Solution

Answer: proved for $q\geq4$ colours (every uniformity $r\geq3$); open for $q=2$ (the literal content of erdosproblems.com #562/#564, with a \$500 prize attached to the $r=3$ case).

The transferable technique — the Erdős–Hajnal stepping-up lemma: encode vertices as binary strings, and read off a higher-uniformity colour from the position where consecutive strings first disagree.

1. Encode $2^N$ vertices as binary strings of length $N$, and order them lexicographically. For any $(k+1)$-tuple of vertices $v_1<v_2<\cdots<v_{k+1}$ (as binary strings), define the difference sequence $\delta_1,\dots,\delta_k$ where $\delta_i$ is the position of the most-significant bit at which $v_i$ and $v_{i+1}$ differ. This sequence carries almost all of the combinatorial information about how the $(k+1)$-tuple sits inside $\{0,1\}^N$. 2. Pull back a $k$-uniform colouring through the difference sequence. Given a "good" (clique-avoiding) $q$-colouring $\chi$ of the $k$-uniform hypergraph on $N$ vertices $\{1,\dots,N\}$, define a colouring $\chi'$ of $(k+1)$-tuples of $\{0,1\}^N$ by $\chi'(v_1,\dots,v_{k+1}) := \chi(\delta_1,\dots,\delta_k)$ — i.e. treat the *bit-positions* where consecutive vertices first disagree as if they were themselves the vertices of a $k$-uniform hypergraph, and copy $\chi$'s colour. 3. Any monochromatic clique in $\chi'$ forces an increasing (or otherwise highly structured) monochromatic clique in $\chi$. This is the heart of the proof: if $\chi'$ is monochromatic on some set of $(k+1)$-tuples, the associated difference sequences form a monochromatic substructure for $\chi$ on the *bit-positions* involved — because the lexicographic order forces the $\delta_i$ sequences arising from any large enough clique to themselves be "sunflower-like" (nested/increasing), which is exactly the extra structure needed to recover a genuine $\chi$-monochromatic clique on $\{1,\dots,N\}$ from it. Precisely quantified, this yields the formula (as stated verbatim in Dubroff–Girão–Hurley–Yap, "Tower Gaps in Multicolour Ramsey Numbers," arXiv:2202.14032, eq. (1)): $$r_{k+1}(2t+k-4;\,q) \;>\; 2^{\,r_k(t;q)-1}\qquad\text{for all }q\text{ and }k\geq3.$$ So a lower bound of size $N=r_k(t;q)-1$ at uniformity $k$ becomes a lower bound of size $2^N$ at uniformity $k+1$ — one entire extra exponential, for free, at the cost of only a linear loss in the target clique size ($t\mapsto 2t+k-4$). 4. Iterate to build the whole tower. Starting from any $r=3$ lower bound of tower-height $h$ and applying the lemma $r-3$ more times (valid for any $q\geq2$ once $k\geq3$) produces an $r$-uniform lower bound of tower-height $h+(r-3)$ — i.e. the lemma converts "one extra level of hypergraph uniformity" into "one extra level of the exponential tower," mechanically, no matter how large $r$ gets. This is why the entire general-$r$ conjecture #562 reduces to the single base case #564 ($r=3$): whatever tower height you can prove at $r=3$, stepping-up hands you for free at every larger $r$, matching level-for-level. 5. The reason $q\geq4$ is needed only for the very first application ($k=2\to3$): the base step of the lemma (lifting an *ordinary graph* colouring to a $3$-uniform one) needs to distinguish more cases in the difference-sequence encoding than $2$ or $3$ colours can carry without collision — with $q\geq4$ colours there is enough room to encode, for each pair $(\delta_1,\delta_2)$, both which of the two graph-colours the "outer" edge $(v_1,v_3)$-analogue receives *and* enough auxiliary bookkeeping to keep the argument sound; this is exactly the extra room Erdős–Hajnal–Máté–Rado [EHMR84] exploit to get $R_3(n;4)\geq2^{2^{cn}}$ directly from the classical $R_2(n;4)=R(n,n;4)\geq q^{cn}$ multicolour graph-Ramsey bound. Once uniformity $3$ is reached, every *subsequent* application of the lemma (uniformity $k\to k+1$ for $k\geq3$) only needs $q\geq2$, because $k$-uniform hyperedges already carry enough internal structure (more than one "difference-sequence slot") to make the encoding unambiguous even in $2$ colours. 6. Why this is the transferable engine for the whole open-problem cluster. Every downstream hypergraph-Ramsey lower-bound question in this family — #562 itself, #564 ($r=3$,$q=2$), the "hedgehog" colour-blindness question, the off-diagonal $r_4(5,n)$ tower-growth results (arXiv:2604.23986, arXiv:2605.04105, cited in erdos/564.md), and the "Tower Gaps" paper's own new *generalized* stepping-up lemmas for $r_k(t;q,p)$ (Dubroff–Girão–Hurley–Yap, Theorem 1.3) — is attacking essentially the same object: can the stepping-up lemma's base step be run with fewer colours, or can a genuinely different construction reach the doubly-exponential rate at $r=3$, $q=2$ directly (bypassing the lemma's colour requirement entirely)? Any improvement to the $q=2$, $r=3$ base case propagates automatically, for free, to every larger uniformity via step 4 above — which is exactly why this 60-year-old base case, not the general-$r$ statement, is where all research effort in this cluster concentrates.

Related

- Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey) — the $r=3$, $q=2$, \$500 special case; per the stepping-up-lemma reduction (step 4 above), resolving #564 alone would settle #562 for every $r\geq4$ simultaneously. The crux case of this entire page's open direction. - Erdős #563 — the graph (t=2) discrepancy-Ramsey function F(n,α) has order Θ_α(log n) — the graph ($t=2$) positive-discrepancy analogue $F(n,\alpha)\asymp_\alpha\log n$; #562 is explicitly the $\alpha=0$ (zero-discrepancy, i.e. exactly-monochromatic) endpoint of the same underlying $F^{(t)}$-type family that #563/#161 generalize to $\alpha>0$. - Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? — the $t$-uniform generalization of #563's discrepancy function $F^{(t)}(n,\alpha)$; sits numerically and thematically beside #562/#563/#564 in Erdős's own Ramsey-theory problem list (#38–#40). - Conlon–Fox–Sudakov 2010 — off-diagonal 3-uniform hypergraph Ramsey numbers $r_3(s,n)$: a near-tight upper bound via an online-Ramsey-game reduction, and the first superexponential lower bound — Conlon–Fox–Sudakov's near-tight *off-diagonal* $r_3(s,n)$ bounds; explicitly flags (in its own Related section) that "no dedicated page yet exists … for this specific numbered conjecture" — the diagonal $r=3,q=2$ gap that this page's Solution identifies as the load-bearing missing base case. - concept/stepping-up-lemma — the binary-string/difference-sequence technique that is this page's entire transferable content; the single tool responsible for every known tower-type hypergraph-Ramsey lower bound since 1965. - concept/tower-function-growth-rate — the $T_k(x)$ bookkeeping ($T_1(x)=x$, $T_{i+1}(x)=2^{T_i(x)}$) used throughout this problem family to state and compare tower-height conjectures. - concept/probabilistic-deletion-construction — Erdős's 1947 random-colouring argument giving the $r=2$ base case $R(n,n)>2^{n/2}$ that anchors the entire induction (via the stepping-up lemma) underlying every lower bound in this page.