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

Statement

For integers $k\ge2$ and $s,n\ge k$, the hypergraph Ramsey number $r_k(s,n)$ is the minimum $N$ such that every red/blue coloring of the $k$-element subsets ($k$-tuples) of an $N$-set contains either a red $s$-set (all its $k$-tuples red) or a blue $n$-set (all its $k$-tuples blue). For $k=2$ this is the classical graph Ramsey number $r(s,n)$, exponentially well understood; already for $k=3$, the state of knowledge before this paper was drastically worse:

- Diagonal case ($s=n$): Erdős–Hajnal–Rado (1965) showed $2^{cn^2} < r_3(n,n) < 2^{2^{c'n}}$ — a gap of one full exponential between lower and upper bound — and conjectured $r_3(n,n) > 2^{2^{cn}}$, with Erdős offering $500 for a proof (or disproof). - Off-diagonal case ($s$ fixed, $n\to\infty$): the best known upper bound, from Erdős–Rado's 1952 stepping-formula $r_k(s,n)\le 2^{\binom{r_{k-1}(s-1,n-1)}{k-1}}$ combined with the graph bound $r(s,n)\le n^{s-1}$, gave $r_3(s,n)\le 2^{cn^{2s-4}/\log^{2s-6}n}$ — while Erdős and Hajnal (1972) had shown only a linear lower bound $\log r_3(4,n)>cn$, and explicitly conjectured (but could not prove) that $\log r_3(4,n)/n\to\infty$, i.e. that the true growth is superlinear, hence very likely superexponential in $N$'s size. - Erdős–Hajnal's $f_k(N,s,t)$ problem (1972): a general open question asking how the "largest guaranteed monochromatic-or-locally-dense" set size interpolates between polynomial and iterated-logarithmic growth as the allowed number $t$ of "bad" blue $k$-tuples in the red side increases from $1$ to $\binom sk$.

Conlon–Fox–Sudakov (arXiv:0808.3760, JAMS 2010) attack the off-diagonal case $r_3(s,n)$ head-on with two new, independent techniques — one for the upper bound, one for the lower bound — closing most of the exponent gap and, critically, resolving the Erdős–Hajnal 1972 question in the affirmative.

Facts

- Source: D. Conlon, J. Fox, B. Sudakov, "Hypergraph Ramsey numbers," arXiv:0808.3760 (27 Aug 2008); *J. Amer. Math. Soc.* 23 (2010), no. 1, 247–266. - New upper bound (Theorem 1.2 / eq. (4)): for fixed $s\ge4$ and $n\to\infty$, $$\log r_3(s,n) \le \Big(\tfrac{s-3}{(s-2)!}+o(1)\Big)\,n^{s-2}\log n,$$ improving the exponent of the 1952 Erdős–Rado bound by a factor of $n^{s-2}/\mathrm{polylog}(n)$. - Diagonal corollary (Theorem 2.4): $\log_2\log_2 r_3(k,k) \le (2+o(1))k$, i.e. $r_3(k,k)\le 2^{2^{(2+o(1))k}}$ — improving Erdős–Rado's classical $r_3(k,k)\le 2^{2^{4k}}$. - New lower bound (Theorem 1.3): there are absolute constants $c_1,c_2>0$ with $$\log r_3(s,n) \ge c_1\, s\, n\, \log(n/s) \qquad\text{for all } 4\le s\le c_2 n.$$ For $s$ constant this is $r_3(s,n)\ge 2^{\Omega(n\log n)}$ — the first superexponential lower bound for off-diagonal 3-uniform hypergraph Ramsey numbers, and it directly confirms $\log r_3(4,n)/n\to\infty$, settling the Erdős–Hajnal 1972 conjecture. It also interpolates continuously to the diagonal bound: at $s=n$ it recovers the Erdős–Hajnal–Rado bound $r_3(n,n)\ge2^{cn^2}$. - Three-color bound (Theorem 1.1): $r_3(n,n,n) \ge 2^{n^{c\log n}}$, a large improvement on Erdős–Hajnal's earlier $2^{cn^2\log^2n}$; obtained via a refinement of the classical Erdős–Hajnal stepping-up lemma seeded with an *off-diagonal* (not diagonal) graph-Ramsey coloring $r(\log_2 n,\,n-1)$, then merging two of the four stepped-up color classes. - Progress on Erdős–Hajnal's 1972 $f_k(N,s,t)$ problem: the function $h_1^{(3)}(s)$ (the threshold $t$ at which growth switches from polynomial-in-$N$ to poly-log-in-$N$) is determined exactly for infinitely many $s$ (all powers of 3), and pinned to within $O(s\log s)$ of $s^3/24$ for every $s$, via a new auxiliary quantity $T(s)$ = the maximum number of cyclic triangles in an $s$-vertex tournament. - Companion papers by the same three authors reuse the machinery of this paper for related hypergraph-Ramsey/discrepancy questions: arXiv:0901.3912 ("Large almost monochromatic subsets in hypergraphs," resolves the $t=3$ case of Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0?) and arXiv:1104.5544 ("Erdős-Hajnal-type theorems in hypergraphs") — both cited from Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? in this wiki.

Solution

Answer. $\log_2\log_2 r_3(n,n)$ is now known to lie in $[cn^2,\,(2+o(1))n]$ after exponentiating once more — i.e. the diagonal gap did not close (Erdős's $500 conjecture remains open), but the *off-diagonal* exponent gap essentially closed: $\log r_3(s,n)$ is now known to within a $\mathrm{polylog}(n)$ factor of $n^{s-2}$ from above, and to be genuinely superexponential ($2^{\Omega(sn\log(n/s))}$) from below whenever $s$ is fixed or grows slowly — resolving the 1972 Erdős–Hajnal linear-growth conjecture.

The transferable technique #1 (upper bound): replace "expose every pair, vote by simple majority" with "expose only what an adaptive online game forces, and bias the vote by the game's own color imbalance."

The classical 1952 Erdős–Rado proof of $r_3(s,n)\le2^{\binom{r(s-1,n-1)}2}$ greedily builds vertices $v_1,\dots,v_h$ and, for every pair $i<j$, determines a derived graph-color $\chi'(v_i,v_j)$ by majority vote ($\alpha=1/2$) over the residual vertex set: it looks at all triples $\{v_i,v_j,w\}$ and colors the pair red if $\ge$ half of them are red. Each such vote halves the residual set, and since all $\binom{r(s-1,n-1)}2$ pairs must be resolved to guarantee the derived 2-coloring contains a monochromatic clique, the bound pays a factor of $2$ per pair, i.e. an exponent of $\binom{r(s-1,n-1)}2\approx n^{2s-4}$.

Conlon–Fox–Sudakov make two independent improvements, formalized in Theorem 2.1 (general bound (5), $r_3(s,n)\le(v+1)\alpha^{-r}(1-\alpha)^{r-m}$) and proved via an explicit binary-string construction (Lemma 2.2):

1. Don't resolve every pair — only what an adaptive game requires. They observe you don't need $\chi'$ defined on *all* $\binom h2$ pairs, only on enough edges to force a monochromatic clique in an online sense. This is captured by the *vertex on-line Ramsey number* $\tilde r(s,n)$: a "builder" reveals vertices one at a time and adaptively chooses which edges to a past vertex to query; a "painter" colors each queried edge red/blue immediately; $\tilde r(s,n)$ is the minimum number of edges builder needs to force a red $K_s$ or blue $K_n$. They give an explicit builder strategy (vertices labeled by binary strings recording the color history) achieving $\tilde r(s,n)\le(s+n-4)\binom{s+n-2}{s-1}+1$ — far fewer edges than $\binom{r(s-1,n-1)}2$. Each exposed edge still costs a factor of (at most) $2$ in the greedy-construction argument, but there are many fewer of them. 2. Bias the vote to match the game's own red/blue imbalance. The online strategy of step 1 uses comparatively few red edges ($r\ll m$, the total edge count) — most of its queried edges resolve blue. Rather than a symmetric $\alpha=1/2$ majority vote (cost factor $2$ per edge regardless of color), CFS use an asymmetric threshold $\alpha\ne1/2$: a pair is declared red only if $\ge\alpha\,|S|$ of the residual triples are red. This makes resolving a *red*-labeled pair expensive (residual set shrinks by factor $\alpha^{-1}$, steep for small $\alpha$) but resolving a *blue*-labeled pair cheap (residual set shrinks by only $(1-\alpha)^{-1}\approx1$). Since the online strategy produces few red edges and many blue edges, tuning $\alpha\approx r/m$ (optimizing $\alpha^{-r}(1-\alpha)^{r-m}$) makes the total cost dramatically smaller than the naive $\alpha=1/2$ choice — this is precisely what turns the exponent from $n^{2s-4}$ into $n^{s-2}\log n$.

Why this is the reusable move. Any greedy/stepping-up-style Ramsey argument that (a) builds an auxiliary lower-uniformity coloring by "resolving" pairs/edges one at a time via a threshold vote over a shrinking residual set, and (b) currently resolves *every* pair symmetrically, can potentially be improved by the same two-part recipe: (i) replace exhaustive pairwise resolution with an adaptive/online-game strategy that only forces the needed monochromatic substructure using far fewer queries (an *online Ramsey number* in place of a static Ramsey number — genuinely smaller in general, as the paper notes the analogous *edge* on-line Ramsey number and the *size* Ramsey number do not give this saving, so the *vertex*-online formulation is the essential ingredient), and (ii) once the strategy's own red/blue query-count asymmetry is known, replace the symmetric-majority threshold with a biased threshold tuned to that asymmetry, turning a fixed multiplicative loss-per-query into a loss weighted by how rarely the expensive outcome actually occurs. This is the template the paper's own diagonal corollary (Theorem 2.4) and its non-complete-hypergraph refinement (Proposition 2.5, on $K_4^{(3)}\setminus e$ vs. $K_n^{(3)}$) both reuse directly.

The transferable technique #2 (lower bound): compose a graph-Ramsey extremal coloring with an independent random re-coloring layer to manufacture a much stronger hypergraph coloring.

Theorem 3.1's construction, for $\ell=n/4$, $r=r(s-1,\ell)-1$, $N=rn/24$:

1. Take an optimal graph-Ramsey coloring $c_1$ of $K_r$ with no red $K_{s-1}$ and no blue $K_\ell$ (existence guaranteed by the *definition* of $r=r(s-1,\ell)-1$) — this is the "palette," of size only $r\approx\ell^{O(1)}$, far smaller than $N$. 2. Independently color every pair of the much larger ground set $[N]$ with one of the $r$ palette-colors uniformly at random — an auxiliary random coloring $c_2:\binom{[N]}2\to[r]$. 3. Compose the two into a 3-uniform coloring: for $a<b<c$, set $\chi(\{a,b,c\})=c_1(c_2(a,b),c_2(a,c))$ if $c_2(a,b)\ne c_2(a,c)$, and blue otherwise. That is, the *disagreement* between two of $c_2$'s random colors is used as a coordinate pair fed into the small palette coloring $c_1$. 4. Red-freeness is deterministic, not probabilistic: any red $s$-clique in $\chi$ would force $s-1$ *distinct* $c_2$-colors forming a red clique in $c_1$'s palette — impossible since $c_1$ has none. No union bound, no failure probability, on this side. 5. Blue-freeness is a first-moment argument: a blue $n$-clique in $\chi$ forces, for each vertex $v_i$ of the clique, fewer than $\ell$ distinct $c_2$-colors among its pairs to later clique vertices (else a blue $\ell$-clique would appear in $c_1$, again impossible). The expected number of blue $n$-cliques under $c_2$'s randomness is then bounded (using $N=r\ell/6$, tuned so the exponent is negative) to be $<1$, so a good coloring exists.

The key structural idea is that step 3's *composition* converts a graph-Ramsey lower bound of size $r$ into a hypergraph-Ramsey lower bound of size $N\approx r^{\Theta(1)}$ — i.e. exponentiates the *quality* (not just the size) of the seed coloring, because the ground set can be blown up polynomially in $r$ while the palette itself stays a genuine (tiny) Ramsey-good coloring, giving a coloring whose blue-clique-avoidance probability, though shrinking, still beats $1/\binom Nn$. This is structurally different from — and, crucially, applicable already at uniformity $k=3$ *directly*, unlike — the classical Erdős–Hajnal stepping-up lemma, which needs $k\ge3$ as its input uniformity to produce output at uniformity $k+1$ and so cannot bootstrap a good $k=3$ bound from nothing. Portable takeaway: whenever a lower-uniformity ("smaller object") Ramsey-type extremal coloring exists, feeding it as the small palette of a random-recoloring composition — index the palette by the *pattern of disagreement* between random auxiliary colors on a much larger ground set — can produce a *provably new* (not merely stepped-up) higher-uniformity lower bound, with the "impossible substructure forces impossible palette substructure" argument staying entirely deterministic and only the complementary direction needing a first-moment probabilistic bound. Theorem 4.1's 3-color bound applies a genuinely different, complementary technique (a refined stepping-up lemma, using an *off-diagonal* seed graph $r(\log_2n,n-1)$ instead of the diagonal $r(n-1,n-1)$, plus a 3-vs-4-color merge trick) — evidence that the paper's overall strategy is to pick, for each specific bound sought, whichever of these two composition/stepping-up-family techniques better exploits the asymmetry of the problem ($s\ll n$ favors the random-composition technique; the 3-color diagonal problem favors an asymmetrized stepping-up).

Related

- Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? — Erdős's 1989 hypergraph-discrepancy jump question; its $t=3$ case is resolved by a companion Conlon–Fox–Sudakov paper (arXiv:0901.3912) using the same authors' dependent-random-choice machinery, cited alongside this paper (arXiv:0808.3760) as background. - Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts — the Fox–Sudakov survey technique (arXiv:0909.3271) used by the *companion* CFS hypergraph papers; this page's paper instead introduces its own two independent techniques (online-Ramsey-game reduction; random-recoloring composition) rather than dependent random choice itself, but both lines are part of the same Conlon–Fox–Sudakov hypergraph-Ramsey research program. - Ramsey-type concentration of the independence/clique number of G(n,1/2) — the parent concept-level pointer for classical graph-Ramsey growth-rate results that this page's $r(s-1,n-1)$ and $r(\log_2n,n-1)$ seed bounds are drawn from. - The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs — the general probabilistic-existence "build random, then argue/delete blemishes" family that Theorem 3.1's blue-freeness step (first-moment bound $<1$) instantiates, here composed with a deterministic red-freeness argument rather than an explicit deletion step. - Erdős–Hajnal–Rado diagonal $500 conjecture ($r_3(n,n)>2^{2^{cn}}$) — explicitly *not* resolved by this paper (the diagonal gap remains a full exponential); flagged as the natural still-open target this paper's off-diagonal techniques have not yet cracked. No dedicated page yet exists in this wiki for this specific numbered conjecture — a natural next page, since it is the load-bearing open ancestor of the entire $r_3(s,n)$ cluster documented here.