Du–Hu–Liu–Wang (Apr 2026), improved by Fan–Li–Lin–Ning (May 2026) — a double-exponential lower bound for $r_4(5,n)$, completing the Erdős–Hajnal 1972 off-diagonal hypergraph-Ramsey tower-growth-rate program

Statement

For $k\ge2$ and $s,n\ge k$, the hypergraph Ramsey number $r_k(s,n)$ is the smallest $N$ such that every $N$-vertex $k$-uniform hypergraph contains either a complete $k$-uniform sub-hypergraph $K_s^{(k)}$ on $s$ vertices, or an independent set of size $n$ (a set of $n$ vertices spanning no edge at all).

The Erdős–Hajnal 1972 conjecture (P. Erdős, A. Hajnal, "On Ramsey like theorems, problems and results," in *Combinatorics* (Proc. Conf. Combinatorial Math., Oxford 1972), pp. 123–140) states that for every fixed $4\le k<s$, $$r_k(s,n) \ge \mathrm{twr}_{k-1}(\Omega(n)),$$ where $\mathrm{twr}_i(x)$ is the tower of exponentials of height $i$ ($\mathrm{twr}_1(x)=x$, $\mathrm{twr}_{i+1}(x)=2^{\mathrm{twr}_i(x)}$) — i.e. that $r_k(s,n)$ grows at the *same* tower height as the classical Erdős–Rado upper bound, one full exponential level higher per unit increase in uniformity $k$, matching the behaviour already known for the diagonal case. Determining this tower growth rate — the height of the tower, as opposed to the exact linear constant inside it — for every classical off-diagonal case $r_k(k+1,n)$ was, as of early 2026, reduced (via monotonicity in $s$ and prior partial results) to exactly two open instances: $k=4$ (i.e. $r_4(5,n)$ and, by monotonicity, $r_4(6,n)$).

The solved problem. Prove $r_4(5,n) \ge 2^{2^{\Omega(n^{c})}}$ for *some* constant $c>0$ — i.e. establish that $r_4(5,n)$ is genuinely double-exponential (tower height 3 counting the base, or $\mathrm{twr}_3(\cdot)$ in the convention above), matching the tower height of the known upper bound, even though the optimal linear exponent $c=1$ conjectured by Erdős–Hajnal remains open.

Facts

- Origin of the conjecture: P. Erdős, A. Hajnal, "On Ramsey like theorems, problems and results," 1972 — the general off-diagonal hypergraph-Ramsey tower-growth-rate conjecture, distinct from (though closely related to, via the same stepping-up-lemma family) the 1965 Erdős–Hajnal–Rado *diagonal* conjecture that is 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) / Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey) ($R_3(n)\ge2^{2^{cn}}$, still open, $500 prize). - First resolution: Longma Du, Xinyu Hu, Ruilong Liu, Guanghui Wang, "A double-exponential lower bound for $r_4(5,n)$," arXiv:2604.23986 (27 Apr 2026): $r_4(5,n)\ge2^{2^{cn^{1/7}}}$ for an absolute constant $c>0$ — the first double-exponential lower bound ever proved for this number. - Improvement five days later, by an independently-working team, then merged into one joint paper: Chunchao Fan, Mingze Li, Qizhong Lin, Bo Ning, "An improved double-exponential lower bound for $r_4(5,n)$," arXiv:2605.04105 (4 May 2026): $r_4(5,n)\ge2^{2^{cn^{1/5}}}$. The paper's own text states the two groups discovered the result independently and "decided to write a joint paper," with the arXiv manuscript primarily based on Fan and Lin's original version. - What "completely solves the tower-growth-rate problem" means precisely: the classical Erdős–Rado stepping-up machinery already gives a matching-height upper bound $r_4(5,n)\le2^{2^{O(n)}}$ (tower height 3), so the missing piece for decades was a lower bound of the *same tower height* — any *single*-exponential lower bound ($2^{\Omega(n^{c})}$, tower height 2) leaves the true growth rate ambiguous between heights 2 and 3. Both 2026 papers close exactly this height-gap: they do not achieve the conjectured linear exponent $c=1$ (still open — genuinely establishing $2^{2^{\Omega(n)}}$, not just $2^{2^{\Omega(n^{1/5})}}$, remains unresolved), but a polynomial exponent inside a double exponential is already enough to fix the tower *height*, which is what "growth rate" means in this tower-function bookkeeping convention. - Why $r_4(5,n)$ was "the crucial remaining case": $r_k(s,n)$ is monotone non-decreasing in $s$, so a double-exponential bound for $r_4(5,n)$ immediately forces the same tower height for $r_4(6,n)$ — the other case explicitly flagged as still open in the papers' own framing of "the last two cases" of the 1972 conjecture. Together with the earlier resolution of the $k=5$ "penultimate case" by D. Mubayi, A. Suk, Y. Zhu, "A note on the Erdős–Hajnal hypergraph Ramsey problem," arXiv:2003.00074 (2020; *Proc. Amer. Math. Soc.* 150 (2022)) — a 5-uniform construction, also via a stepping-up-lemma variant — this leaves no remaining open case in the $r_k(k+1,n)$ tower-growth-rate family for any fixed $k\ge3$ (the $k=3$ off-diagonal case, $r_3(s,n)$, was already settled by Conlon–Fox–Sudakov 2010, see 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). - What is explicitly still open: the exact linear-in-$n$ exponent — Erdős–Hajnal's conjectured $r_4(5,n)\ge2^{2^{\Omega(n)}}$ — is not implied by either 2026 paper; only the tower *height* is settled. This mirrors the still-fully-open diagonal sibling Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey) ($R_3(n)\ge2^{2^{cn}}$, $500), which the Mubayi–Suk survey explicitly notes is logically *upstream of* (implies, but is not implied by) a double-exponential bound for $r_4(5,n)$ — so this 2026 breakthrough resolves a *downstream*, independently-provable relative of #564, not #564 itself.

Solution

Answer. $r_4(5,n)\ge2^{2^{c\,n^{1/5}}}$ for an absolute constant $c>0$ (Fan–Li–Lin–Ning 2026, improving Du–Hu–Liu–Wang 2026's original $2^{2^{cn^{1/7}}}$) — the first genuinely double-exponential lower bound for $r_4(5,n)$, settling the tower growth rate of $r_k(k+1,n)$ for every $k$ and thereby completing the classical off-diagonal branch of the Erdős–Hajnal 1972 hypergraph-Ramsey program.

**The transferable technique — build the coloring by *explicit construction*, not probabilistic deletion, using a chain of "greedy local-maxima" layers to squeeze a usable monotone substructure out of an arbitrary large independent set:**

1. Start from a known lower-uniformity "good" 2-coloring, not from randomness. The construction is *explicit*: it builds a 4-uniform hypergraph $H$ on a vertex set that is itself a specially-structured sequence (encoding "gaps" between consecutive elements), seeded by a 2-coloring $\phi$ of pairs that is known (via a "good triple" lemma, proved separately and reused as a black box) to force a strong monotone-color-mismatch property on every sufficiently large subset. This is the same broad family as the classical Erdős–Hajnal binary-string stepping-up lemma (concept/stepping-up-lemma) — encode vertices/gaps so that a $k$-tuple's color depends only on the relative order and induced coloring of a handful of "first-difference" gap values — but instantiated with a bespoke coloring rule (three explicit case-based edge-definition rules keyed on whether a triple of gaps is monotone or forms a "valley," and whether $\phi$ matches or mismatches across the relevant pairs) tuned specifically to forbid $K_5^{(4)}$ deterministically, with no probabilistic deletion step anywhere — every edge of $H$ is defined by an explicit case rule, and $K_5^{(4)}$-freeness is proved by a closed case analysis (five vertices inducing $K_5^{(4)}$ would force mutually contradictory color constraints from the three rules), not by a first-moment/union-bound argument. 2. The real bottleneck is bounding the independence number, and that is where the improvement lives. Given a large candidate independent set $Q$ (size $m$), the proof must show $H$ still has an edge inside $Q$ once $m$ passes a threshold. It does this by extracting, from the raw sequence of gaps in $Q$, a nested chain of "local maxima" layers $\Delta^{(0)}\supset\Delta^{(1)}\supset\cdots\supset\Delta^{(t)}$: $\Delta^{(0)}$ is all gaps in $Q$, and each subsequent $\Delta^{(i)}$ is the (greedily selected) sequence of local maxima of $\Delta^{(i-1)}$ — indices $\delta_j$ whose immediate neighbors in the previous layer are both smaller. Each greedy-maxima pass shrinks the usable index set by roughly a factor of $2n$, but *guarantees* the surviving values retain a strict monotone-comparison structure carried down from the original coloring property. After enough layers, the survivors are forced — by the seed coloring's "good triple" property — into a configuration that itself satisfies one of the three edge-defining case rules, producing a contradiction (an edge inside the supposedly-independent $Q$). 3. **The exponent is a direct, mechanical function of the layer count — this is *the* lever the improvement pulls. The original Du–Hu–Liu–Wang argument needed seven greedy local-maxima layers to reach a forced contradiction, and each layer costs a $\Theta(1/n)$-type loss in the final polynomial exponent, yielding overall $r_4(5,n)\ge2^{2^{\Omega(n^{1/7})}}$. Fan–Li–Lin–Ning's entire technical contribution was to re-examine the case analysis and show only five layers are actually needed — a purely structural tightening of the same argument, not a new construction or a different coloring rule — mechanically improving the bound to $2^{2^{\Omega(n^{1/5})}}$. This is the single most transferable, reusable lesson of the whole result**: in a greedy-layered/iterated-local-maxima stepping-up argument, the number of layers is not incidental bookkeeping — it is *exactly* the reciprocal of the final polynomial exponent, so the highest-leverage way to improve such a bound is to hunt for redundancy in the case analysis that lets one or more layers be eliminated, rather than to redesign the construction from scratch. 4. Portable recipe for the next open case in this family. (a) Identify (or import as a black box) a "good" lower-dimensional coloring with a provable monotone/mismatch forcing property on large subsets — exactly the role Lemma 3.1 plays here. (b) Define the target higher-uniformity edge set via a small, closed set of explicit case rules on gap-monotonicity and induced-color agreement, engineered so a forbidden clique forces a contradiction among the rules — no randomness needed for the clique-freeness side. (c) To bound independence, build a greedy chain of local-maxima layers and *count how many layers a full case-analysis actually requires* to force a contradiction; treat that layer-count as the quantity to optimize, since it converts directly and mechanically into the final polynomial exponent inside the double exponential. (d) Check monotonicity of the target Ramsey function in its clique-size parameter before starting: resolving the smallest genuinely-open case (here $s=k+1=5$) can immediately dispose of nearby larger-$s$ cases (here $s=6$) for free.

Related

- Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey) — Erdős–Hajnal–Rado's 1965 diagonal conjecture $R_3(n)\ge2^{2^{cn}}$ ($500 prize, still fully open); its own wiki page already forward-links to this exact solved problem as "the closest live solved sibling," and notes the logical direction is one-way (#564 would imply a double-exponential $r_4(5,n)$ bound, not vice versa) — so this 2026 result is a genuinely independent breakthrough, not a corollary of #564. - 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) — the general $r$-uniform diagonal tower-growth conjecture $\log_{r-1}R_r(n)\asymp_r n$; the off-diagonal 1972 conjecture solved here is a structurally adjacent but distinct problem in the same stepping-up-lemma family. - 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 2010 resolution of the $k=3$ off-diagonal growth rate ($\log r_3(s,n)\asymp n^{s-2}\log n$, no tower involved yet at $k=3$); the $k=4$ case documented on this page is the next uniformity level up, where towers first appear. - Conlon–Fox–Sudakov (2011/2012) — the Erdős–Hajnal conjecture has a tripartite 3-uniform analogue, and provably NO clique/independent-set analogue for k>3 and Erdős–Hajnal conjecture: forbidding one induced subgraph forces polynomial-size cliques/independent sets — the *graph-level* (induced-subgraph) Erdős–Hajnal conjecture and its hypergraph analogue; a different (though same-named-author) conjecture from the 1972 off-diagonal tower conjecture solved here — flagged in both pages to avoid confusion between "Erdős–Hajnal conjecture" (induced subgraphs, 1977) and "Erdős–Hajnal 1972 off-diagonal hypergraph-Ramsey tower conjecture" (this page). - concept/stepping-up-lemma — the classical Erdős–Hajnal binary-string tower-type lower-bound machine that this page's greedy-local-maxima construction is a bespoke, heavily case-engineered descendant of; no dedicated concept page yet exists in this wiki for the classical version, a natural next page since it is now cited as a load-bearing ancestor by at least four pages in this cluster (this page, Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey), 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), Conlon–Fox–Sudakov (2011/2012) — the Erdős–Hajnal conjecture has a tripartite 3-uniform analogue, and provably NO clique/independent-set analogue for k>3). - Mubayi–Suk–Zhu, arXiv:2003.00074 — the 2020 resolution of the $k=5$ "penultimate" case of the same 1972 program, via an analogous stepping-up-lemma-based 5-uniform construction; the direct predecessor whose remaining gap ($k=4$) this page's papers close.