Mubayi–Suk–Zhu 2020 — the penultimate case $t=k-1$ of the Erdős–Hajnal 1972 tower-growth conjecture, via an enhanced stepping-up lemma

Statement

For integers $2\le k<n$, let $r_k(k+1,t;n)$ be the minimum $N$ such that every red/blue coloring of the $k$-tuples of $[N]$ contains either a set of $k+1$ integers with at least $t$ of its $k$-tuples colored red, or a set of $n$ integers with all of its $k$-tuples colored blue. (Erdős and Hajnal introduced this function — their notation differed — in "On Ramsey like theorems, problems and results," *Combinatorics* (Proc. Conf. Combinatorial Math., Oxford, 1972), pp. 123–140, as a tool for understanding the harder classical problem $r_k(k+1,n)=r_k(k+1,k+1;n)$.)

Erdős and Hajnal showed $r_k(k+1,t;n) < \mathrm{twr}_{t-1}(n^{O(1)})$ for every $t\in\{2,\dots,k\}$ and conjectured the matching lower bound: $$r_k(k+1,t;n) = \mathrm{twr}_{t-1}\!\big(n^{\Theta(1)}\big), \qquad (1)$$ where $\mathrm{twr}_1(x)=x$, $\mathrm{twr}_{i+1}(x)=2^{\mathrm{twr}_i(x)}$ — i.e. the tower height as a function of $t$ is exactly right, not just the crude upper-bound tower.

Prior to 2020 this was known only for $k\le3$, for $t\le3$ (Erdős–Hajnal themselves), and — via Mubayi and Suk's 2016/2018 work — for all $3\le t\le k-2$ when $k\ge5$. That left two cases open: $t=k-1$ ("penultimate") and $t=k$ (equivalent, per Erdős–Hajnal's own remark, to determining the tower height of the classical Ramsey number $r_k(k+1,n)$ itself — the genuinely last, hardest case).

Facts

- Source: D. Mubayi, A. Suk, E. Zhu, "A note on the Erdős-Hajnal hypergraph Ramsey problem," arXiv:2003.00074 (28 Feb 2020). - Main theorem (Thm 1.2). For $k\ge4$, $$r_k(k+1,k-1;n) = \mathrm{twr}_{k-2}\!\big(n^{\Theta(1)}\big),$$ settling conjecture (1) for $t=k-1$ — this significantly improves the previous lower bound, which was "one exponential less" (Mubayi–Suk 2018, BLMS 50). - Base case (Thm 2.2), the real work: there is an absolute constant $c>0$ with $$r_5(6,4;n) > 2^{2^{cn^{1/4}}},$$ i.e. a 5-uniform hypergraph on $\ge 2^{2^{cn^{1/4}}}$ vertices, independence number $\le n$, with every 6-vertex set spanning at most 3 red 6-choose-5 edges. This double-exponential rate is sharp (matches the known upper bound up to the exponent of $n$). - Corollary 1.3 (falls out immediately): $r_k(k+1,k;n) > \mathrm{twr}_{k-2}(n^{\Theta(1)})$ — a new lower bound for the genuinely last case $t=k$, now only "one exponential off" from the known upper bound $\mathrm{twr}_{k-1}(n^{O(1)})$. - How the base case propagates to all $k$: Theorem 2.1, quoted from Mubayi–Suk's earlier paper ("Theorem 7" of Bull. Lond. Math. Soc. 50 (2018), 189–201), is the *stepping-up formula* $r_k(k+1,t;2kn) > 2^{\,r_{k-1}(k,t-1;n)-1}$ for $k\ge6,\ t\ge5$. Plugging the new $k=5,t=4$ double-exponential base bound (Thm 2.2) into this recursion mechanically produces the full tower-height result for every $k\ge4$ — the entire content of the paper is proving the *one new base case* $r_5(6,4;n)$, everything else is the already-known lifting machine. - Status of the family after this paper: the *only* case of (1) left open is $t=k$, equivalent to the tower height of $r_k(k+1,n)$ itself — explicitly flagged by the authors as the target their new techniques are aimed at next. - Predecessor: D. Mubayi, A. Suk, "The Erdős-Hajnal hypergraph Ramsey problem," arXiv:1602.08716, J. Eur. Math. Soc. (to appear) — settled $r_k(s,n)$ for $s\ge k+2$ (a related off-diagonal problem from the same 1972 paper) and cases $3\le t\le k-2$ of (1), via the classical one-shot stepping-up lemma; left $t\in\{k-1,k\}$ open specifically because that lemma, applied directly, loses too much.

Answer

conjecture (1) is TRUE for $t=k-1$: $r_k(k+1,k-1;n)=\mathrm{twr}_{k-2}(n^{\Theta(1)})$, for every $k\ge4$.

**The transferable technique: pushing the classical Erdős–Hajnal *stepping-up lemma* one level further by replacing its usual single mechanical iteration with a purpose-built, structurally richer base coloring plus a genuinely new recursive "local maxima of local maxima" extraction argument to control what the lifted coloring can still encode.**

1. Reduce to a single new base case via the existing stepping-up recursion. The stepping-up lemma is Erdős–Hajnal's classical device: encode $N=2^{2^{cn}}$ vertices as binary strings, and for $u\ne v$ let $\delta(u,v)$ be the position of the most significant bit where they differ. A coloring $\phi$ of *pairs* on a small ground set can then be "lifted" to a coloring $\chi$ of *higher-uniformity tuples* on the binary-string vertex set by reading off $\chi(v_1,\dots,v_k)$ from the pattern of consecutive $\delta$-values $\delta(v_i,v_{i+1})$ — this is what turns a graph coloring into a 5-uniform hypergraph coloring here. Mubayi–Suk's 2018 result already packages one clean iteration of this as the black-box formula $r_k(k+1,t;2kn) > 2^{r_{k-1}(k,t-1;n)-1}$ (their Theorem 7), so the entire multi-$k$ result reduces to proving exactly one new base inequality, $r_5(6,4;n) > 2^{2^{cn^{1/4}}}$ — everything for general $k\ge4$ then follows by mechanically re-applying the same known lifting formula. 2. Design a richer base-graph coloring than "just random." The base object is a 2-coloring $\phi$ of pairs of $\{0,\dots,\lfloor2^{cn}\rfloor\}$, built by the probabilistic deletion method (random coloring + first-moment/Markov argument over both a 3-disjoint-set forbidden pattern *and* a forbidden 4-tuple "bad" pattern), but with two simultaneous structural avoidance properties (Lemma 2.3, parts 1 and 2) baked in rather than one — part 1 rules out three disjoint $n$-sets $A,B,C$ admitting a red/blue bijection pattern between them (needed later to rule out large blue cliques after lifting), part 2 rules out an $n$-set containing a specific "bad" red/blue 4-tuple pattern using a partial Steiner $(n,4,2)$-system to get near-independence between the $\binom n4$ events, which is what lets the union bound close at all. This dual-property base coloring is the first new ingredient — a stronger base gadget than earlier stepping-up applications needed, engineered specifically so the *lifted* 5-uniform coloring can be shown, after lifting, to avoid both "4 red edges among any 6 vertices" and "a large blue clique." 3. Lift with a case-driven (not formulaic) red/blue rule. The 5-uniform coloring $\chi$ is not a single lifted rule but four separate red-triggering conditions on the ordering pattern of $\delta_1,\dots,\delta_4$ (monotone-and-bad, or one of three "valley/peak" patterns using $\phi$), chosen so that a brute-force but exhaustive 8-case Ramsey-style case split over all $2^4=16$ orderings of 5 consecutive $\delta$-values (using Properties I–IV of the binary-difference function $\delta$, e.g. that $\delta(v_1,v_r)=\max_j\delta(v_j,v_{j+1})$) shows no 6 vertices can carry 4 red edges. This case analysis is mechanical once set up, but the rule itself had to be hand-designed against the specific base-coloring properties from step 2 to make the case analysis close. 4. The genuinely new idea — recursively extract "local maxima of local maxima." The hard direction is ruling out a large blue clique. A putative blue clique of size $m=128n^4$ gives a sequence of $m-1$ consecutive $\delta$-values; Property IV shows any long *monotone run* in this sequence would directly hand back a forbidden pattern in the base coloring $\phi$ (via Lemma 2.4), so the sequence must be "choppy." The paper's key move is to iterate this: extract a subsequence of $32n^3$ consecutive local extrema, then restrict to just the local *maxima* among those ($16n^2$ of them), argue those too cannot contain a long monotone run (again forbidden by $\phi$), and then run a delicate recursive "greedy largest-so-far" partitioning ($S_r,T_r$ sets built by repeatedly taking the current maximum of a shrinking window and assigning it to a left- or right-growing set) to find one local maximum $\delta_{j_k}$ that dominates its entire local neighborhood of width $8n$. Splitting the neighboring local *minima* around that dominant peak into two halves $A,B$ of size $\ge n$ each, and using that every pair $(a,b)\in A\times B$ forces a blue 5-tuple in $\chi$ (hence a $\phi(\delta_a,\delta_b)$ constraint), reconstructs exactly the "3 disjoint $n$-sets with a red/blue bijection pattern" that part 1 of Lemma 2.3 was built to forbid — closing the contradiction. This nested local-maxima-of-local-maxima extraction (rather than a single pass) is what the authors flag explicitly in their own introduction as a "crucial new ingredient" to the stepping-up method. 5. Why this is the reusable part. The paper's own concluding remarks state the point directly: they "develop several crucial new ingredients to the stepping up method," specifically the two-property base coloring (Lemma 2.3 part 1) and the recursive local-maxima analysis, and say plainly "it is plausible that these new ideas can be further enhanced to determine the tower height of $r_k(k+1,n)$" — i.e. to crack the one remaining case $t=k$. The transferable lesson for downstream problems is: the classical stepping-up lemma is not a one-shot black box that saturates at some fixed reach — its reach can be extended by (a) hand-engineering a base coloring with more simultaneous forbidden-pattern properties than the minimum needed for one lifting step, and (b) replacing a single pass of "find one long monotone run" with a recursive, nested extraction of local extrema at successively coarser scales until a single dominating peak isolates the exact combinatorial structure the base coloring was built to forbid. Any problem in this cluster that currently stalls because "the standard stepping-up lemma only gets you one level" is a candidate for this same two-part enhancement.

Related

- Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey) — the sibling, still fully open diagonal $2$-colour case of the closely related Erdős–Hajnal–Rado 1965 tower conjecture, $R_3(n)\ge2^{2^{cn}}$, Erdős's own \$500 problem; distinct from (1) but from the same author-pair research program on tower-type hypergraph Ramsey growth, and explicitly cited alongside this paper in that page's own provenance chain. - 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, $q$-colour tower conjecture $\log_{r-1}R_r(n;q)\asymp_{r,q}n$: solved for $q\ge4$ via the *classical* one-shot stepping-up lemma, still open for $q=2,3$ — the cleanest illustration of exactly how far the *unenhanced* stepping-up lemma reaches on its own, against which this page's enhanced version should be contrasted. - 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 2010, a different Erdős–Hajnal 1972 open question ($\log r_3(4,n)/n\to\infty$) resolved via an unrelated technique (online-Ramsey-game upper bound + graph-Ramsey-composition lower bound), showing this same 1972 proceedings paper seeded several independently-solved sub-problems. - concept/stepping-up-lemma — the classical Erdős–Hajnal binary-encoding device ($\delta(u,v)=$ position of most-significant differing bit) this paper's entire construction is built on and extends; not yet written in this wiki as of this page (a natural next concept page, anchored from here and from 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 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). - concept/probabilistic-deletion-method — the first-moment/Markov-inequality construction of the base graph coloring $\phi$ in Lemma 2.3, using a partial Steiner $(n,4,2)$-system to obtain near-independence of the "bad 4-tuple" events.