Large almost monochromatic subsets in hypergraphs (Conlon–Fox–Sudakov, 2009) — resolves the t=3 case of Erdős–Hajnal's 1989 discrepancy problem (Erdős #161)

Statement

Erdős–Hajnal's 1989 question (Erdős, A. Hajnal, "Ramsey-type theorems," *Discrete Appl. Math.* 25 (1989), 37–52), as quoted and framed in arXiv:0901.3912 §1: Erdős and Hajnal had shown that every $2$-coloring of the triples of an $N$-element set contains a subset $S$ of size $s>c(\log N)^{1/2}$ such that at least $(1/2+\epsilon)\binom s3$ triples of $S$ have the same color — i.e. some fixed positive deviation from density $1/2$ is unavoidable at that scale. Erdős then asked (and offered to be persuaded he was *wrong* about $r_3(n)$ being doubly-exponential by an affirmative answer to) the sharper question: does every $2$-coloring (or $\ell$-coloring) of the triples of an $N$-set contain a subset of size $s=c(\epsilon)(\log N)^\delta$, for an absolute constant $\delta>0$, with at least $(1-\epsilon)\binom s3$ triples the same color (for *every* $\epsilon>0$, not just some fixed deviation)? Erdős and Hajnal conjectured this might hold even with $\delta=1/2$.

This is Erdős problem #161 in the $F^{(t)}(n,\alpha)$-jump formulation on erdosproblems.com: writing $F^{(t)}(n,\alpha)$ for the smallest $m$ such that some $2$-coloring of the $t$-tuples of $[n]$ has every $|X|\ge m$ containing $\ge\alpha\binom{|X|}{t}$ $t$-subsets of each color, Erdős asked whether, as $\alpha$ ranges over $[0,1/2)$, $F^{(t)}(n,\alpha)$ jumps discontinuously only once, at $\alpha=0$ (see Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? for the full multi-decade framing, including the general-$t$ status). The paper reviewed here settles this affirmatively for $t=3$.

Facts

- Authors: David Conlon (St John's College, Cambridge), Jacob Fox (Princeton), Benny Sudakov (UCLA). arXiv:0901.3912, submitted 25 Jan 2009; published *Israel Journal of Mathematics* 181 (2011), 423–432. - Companion/prerequisite papers by the same three authors on the same machinery: "Hypergraph Ramsey numbers," arXiv:0808.3760 (JAMS 2010) and "Erdős-Hajnal-type theorems in hypergraphs," arXiv:1104.5544 (JCTB 2012) — the latter shows the natural Erdős–Hajnal (induced-subgraph) analogue of this phenomenon fails for $k$-uniform hypergraphs with $k>3$, a structural reason the general-$t$ case of Erdős #161 stays open. - Sits in erdosproblems.com's registry as resolving the $t=3$ special case of the still-open ($t\ge4$) Erdős #161 (see Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0?); the site marks #161 overall as open (a \$500 problem) precisely because this paper's technique has not been extended past $t=3$.

Solution

Answer: yes, and with the conjectured optimal exponent $\delta=1/2$.

> Theorem 1 (arXiv:0901.3912). For each $\epsilon>0$ and each number of colors $\ell$, there is $c=c(\ell,\epsilon)>0$ such that every $\ell$-coloring of the triples of an $N$-element set contains a subset $S$ of size $s=c\sqrt{\log N}$ such that at least $(1-\epsilon)\binom s3$ triples of $S$ have the same color.

This is tight up to the constant $c$: a uniformly random $\ell$-coloring of the triples of $[N]$ has, with high probability, every subset of size $\gg\sqrt{\log N}$ already $(1/\ell+o(1))$-balanced across colors, by a standard binomial tail bound — so no coloring can force almost-monochromatic subsets larger than $\Theta(\sqrt{\log N})$.

The striking corollary (contrasting hypergraphs with graphs): for $\ell\ge3$ colors there exist $\ell$-colorings of the triples of $[N]$ whose *fully* monochromatic subsets have size only $\Theta(\log\log N)$ (or, for $\ell\ge4$, via Erdős–Hajnal's classical construction) — yet Theorem 1 forces an *almost*-monochromatic subset of size $\Theta(\sqrt{\log N})$, exponentially larger. In graphs the two quantities (monochromatic vs. almost-monochromatic subset size) have the *same* order of magnitude; hypergraphs decouple them completely.

The transferable technique: KST-powered "block stepping-up" of Erdős–Rado

Theorem 1 is deduced as an immediate corollary of a Ramsey-number bound for complete multipartite 3-uniform hypergraphs:

> Theorem 2. The $\ell$-color Ramsey number of the complete $d$-partite $3$-uniform hypergraph $K_d^3(n)$ (vertex set split into $d$ parts of size $n$, edges = all triples touching $3$ different parts) satisfies > $$r(K_d^3(n);\ell)\ \le\ 2^{\ell^{2r}n^2},\qquad r=r_2(d-1;\ell)\ (\text{the ordinary $\ell$-color graph Ramsey number of }K_{d-1}).$$

Since $K_d^3(n)$ has edge density $\to1$ as $d\to\infty$ (density $>1-3/d$), a monochromatic copy *is* an almost-monochromatic set, and choosing $d=\Theta(1/\epsilon)$ turns Theorem 2's bound directly into Theorem 1's $\sqrt{\log N}$.

The proof idea — and this is the reusable move. The classical Erdős–Rado argument for hypergraph Ramsey numbers builds a sequence of *single vertices* $v_1,\dots,v_{r+1}$ greedily: having picked $v_1,\dots,v_i$, it maintains a shrinking "reservoir" $S_i$ such that every triple $\{v_a,v_b,w\}$ ($a<b\le i$, $w\in S_i$) already has a fixed color $\chi(v_a,v_b)$; the reservoir is repeatedly bisected ($S_i\to S_i/2$) by pigeonhole each time a new vertex is added and tested against each earlier vertex. This gives only the tower-type Erdős–Rado bound, because the reservoir loses a factor of $2$ at each of the $\binom{r}{2}$-many vertex pairs.

Conlon–Fox–Sudakov's innovation: replace single vertices by disjoint growing subsets, and replace the naive pigeonhole bisection by the Kővári–Sós–Turán (KST) double-counting technique, so that each round shrinks the reservoir only *polynomially* (in fact by a factor tied to $\sqrt{\log N}$, not by successive halvings across $\binom r2$ steps):

1. Two KST lemmas as the engine. Lemma 1: a bipartite graph on parts $A,B$ with $\ge|A||B|/\ell$ edges contains a complete bipartite subgraph with $a=|A|/\ell$ vertices in $A$ and $b=2^{-|A|}|B|$ vertices in $B$ (via convexity of $\binom{x}{a}$ + pigeonhole over the $2^{|A|}$ subsets of $A$ — the classic KST/Zarankiewicz double-counting move). Lemma 2: a graph on $n$ vertices with $\epsilon n^2$ edges contains $K_{s,t}$ with $s=\epsilon^t n$ for $t<\epsilon n$ (same convexity + pigeonhole trick, one-sided). 2. Stepping up "vertex" to "block." Instead of one vertex $v_{i+1}$ per round, the construction builds a *set* $V_{i+1}$ per round, growing $r+1$ disjoint sets $V_1,\dots,V_{r+1}$ each of final size $n$ from an $N=2^{\ell^{2r}n^2}$-vertex host. In round $i+1$: for each already-built block $V_{h,i}$ ($h\le i$), pigeonhole first isolates a majority color $\chi(h,i+1)$ among triples with one vertex in $V_{h,i}$ and two in the current reservoir $S_i$; then Lemma 1 is applied to the auxiliary bipartite graph (one side $=V_{h,i}$, other side $=$ pairs from $S_i$, edges $=$ "triple has color $\chi(h,i+1)$") to *simultaneously* shrink $V_{h,i}$ down to $V_{h,i+1}=V_{h,i}/\ell$ and extract a dense subgraph $G_{h,i}$ of the reservoir's pair-graph on which the color guarantee now holds for the *whole* new block, not just one vertex. Iterating this over all $h\le i$ compounds the dense subgraphs $G_{i,i}\subset\cdots\subset G_{1,i}$, whose edge count only degrades doubly-exponentially slowly (from $2^{-2^{-j}\ell^{-i}\sqrt{\log N}}$-type bounds, telescoping to $2^{-\sqrt{\log N}}$ after all $i$ steps) — the KST double-counting is what keeps this loss *sub-linear per round* instead of a flat $1/2$-per-step Erdős–Rado bisection. 3. Closing the reservoir with Lemma 2. After all $i$ sub-steps of round $i+1$, Lemma 2 is applied to the surviving dense graph $G_{i,i}$ (with $\epsilon=2^{-\sqrt{\log N}}$, $t=\ell^{-(i+1)}\sqrt{\log N}$) to peel off the next block $V_{i+1,i+1}$ *and* a fresh reservoir $S_{i+1}$ that is still polynomially large ($|S_{i+1}|\ge N^{1/4+2^{-(i+1)}}$) — this quantitative bookkeeping (an explicit induction on $|S_i|\ge(v+1-a)\cdot(\text{product of }\alpha,1-\alpha\text{ factors})$, borrowed in spirit from the sister paper's vertex on-line Ramsey game bookkeeping) is exactly what turns "some shrinkage per round" into a final reservoir size that only needs to survive $r=r_2(d-1;\ell)$ rounds, not $\binom{r}{2}$ pairwise tests. 4. Finish with ordinary graph Ramsey. After $r$ rounds, the induced coloring $\chi$ on pairs $\{1,\dots,r\}$ is an ordinary $\ell$-colored graph; by definition of $r=r_2(d-1;\ell)$ it has a monochromatic clique of size $d-1$, which (together with one more leftover block from the reservoir) assembles into a monochromatic $K_d^3(n)$ in the original coloring.

Why this is the transferable idea. The generic recipe — *(a) take a classical Erdős–Rado-style greedy vertex-by-vertex construction with a shrinking reservoir; (b) upgrade "vertex" to "growing disjoint block" so that one Ramsey-type conclusion is extracted per block instead of per vertex; (c) replace the naive per-step pigeonhole bisection with a Kővári–Sós–Turán double-counting lemma so that many blocks can be built while the reservoir shrinks only sub-exponentially* — is exactly what compresses the number of "lossy" rounds from $\binom{r}{2}$ pairwise vertex-tests down to $r$ block-rounds, and is what buys the exponential improvement from tower/$\log\log$-type bounds down to $\sqrt{\log N}$. The authors flag in their Concluding Remarks that the same scheme gives, for all uniformities $k\ge4$, an almost-monochromatic subset of size $(\log N)^{\delta(k,\ell,\epsilon)}$ — but with $\delta$ now depending on $\epsilon$ (not absolute), which is exactly where the technique currently runs out of steam and where Erdős #161 remains open for $t\ge4$ (see Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0?).

Related

- Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? — the parent open problem (Erdős's \$500 discrepancy-jump question); this paper resolves exactly the $t=3$ case, leaving $t\ge4$ open. - 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 Erdős–Hajnal–Rado hypergraph Ramsey growth-rate conjecture governing the $\alpha=0$ endpoint that this paper's $\alpha>0$ result is contrasted against. - Erdős #563 — the graph (t=2) discrepancy-Ramsey function F(n,α) has order Θ_α(log n) — the $t=2$ (graph) analogue of the same discrepancy-jump question, where the corresponding bound is classical ($F(n,\alpha)\asymp_\alpha\log n$) and the phenomenon of monochromatic $\ll$ almost-monochromatic seen here for hypergraphs does *not* occur. - 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 broader Fox–Sudakov toolkit of common-neighborhood/blow-up techniques that this same author trio uses elsewhere in the hypergraph-Ramsey program (arXiv:0808.3760, arXiv:1104.5544); this specific paper's engine is the more elementary Kővári–Sós–Turán double-counting lemma rather than the dependent-random-choice basic lemma, but both share the "extract a rich/dense substructure, then greedily assemble" shape. - Kővári–Sós–Turán theorem: the double-counting bound ex(n,K_{s,t}) = O(n^{2-1/s}) — the Kővári–Sós–Turán / Zarankiewicz double-counting technique whose two-lemma packaging (Lemma 1: complete-bipartite extraction; Lemma 2: Zarankiewicz-type $K_{s,t}$ bound) is the concrete load-bearing engine of the block-stepping-up construction described above. - Greedy pointwise-extension argument exploiting shared interior points of APs — the classical Erdős–Rado greedy vertex-by-vertex reservoir construction that this paper's "block stepping-up" directly generalizes.