Hypergraph discrepancy and the Erdős–Spencer/Erdős–Hajnal function F^(t)(n,α)

Statement

"Hypergraph discrepancy" covers two distinct but related notions, both tracing to Erdős/Spencer-era probabilistic combinatorics. This page centers on the second (the Erdős–Spencer/Erdős–Hajnal function this wiki's Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? and Erdős #563 — the graph (t=2) discrepancy-Ramsey function F(n,α) has order Θ_α(log n) are about), and gives the first as essential context/contrast.

(A) Classical vertex-coloring hypergraph discrepancy (Beck, Spencer; the more common meaning of the phrase in the wider discrepancy-theory literature). For a hypergraph $H=(V,E)$ and a coloring $\chi:V\to\{-1,+1\}$, define $$\mathrm{disc}(H,\chi) := \max_{e\in E}\Big|\sum_{v\in e}\chi(v)\Big|,\qquad \mathrm{disc}(H):=\min_\chi \mathrm{disc}(H,\chi).$$ The goal is to 2-color the vertices so that every hyperedge is as close to evenly split as possible.

(B) The Erdős–Spencer/Erdős–Hajnal discrepancy-Ramsey function $F^{(t)}(n,\alpha)$ (erdosproblems.com/161, citing [Er90b, p.21]; direct fetch, 2026-07-02): for $\alpha\in[0,1/2)$ and $n,t\ge1$, $$F^{(t)}(n,\alpha) := \text{the smallest } m \text{ such that we can 2-colour the edges of the complete } t\text{-uniform hypergraph on } n \text{ vertices}$$ so that every $X\subseteq[n]$ with $|X|\ge m$ contains at least $\alpha\binom{|X|}{t}$ many $t$-subsets of each colour. Here the coloring is applied directly to the edges (the $t$-subsets themselves), and the question is: how large must a vertex-subset be before it is *guaranteed* to be reasonably color-balanced, for a coloring chosen to make this threshold as small as possible? Erdős's question (#161, $500 prize): for fixed $n,t$, as $\alpha$ ranges over $[0,1/2)$, does $F^{(t)}(n,\alpha)$ increase continuously, or are there jumps — and is there only one jump?

The $t=2$ (graph) case is erdosproblems.com/563's $F(n,\alpha)$: smallest $m$ such that some 2-coloring of $E(K_n)$ has every $X$, $|X|\ge m$, containing $>\alpha\binom{|X|}{2}$ edges of each colour.

$\alpha=0$ specializes to classical Ramsey numbers: requiring $X$ to have *any* edge of each colour (once $\alpha\binom{|X|}{t}>0$ is replaced by the $\alpha\to0$ limit "not monochromatic") is exactly asking $X$ not to be a monochromatic clique, so $F^{(t)}(n,0)$ is (up to the usual $\pm1$ conventions) the $t$-uniform Ramsey function.

Facts

- Origin: the discrepancy-in-hypergraphs question traces to Erdős and Hajnal, 1989 (per Conlon–Fox–Sudakov's abstract, arXiv:0901.3912: their theorem "answers an open question of Erdős and Hajnal from 1989 on discrepancy in hypergraphs"); Erdős and Hajnal's own earlier result was that every 2-coloring of the triples of an $N$-set contains a subset $S$ of size $s>c(\log N)^{1/2}$ with $\ge(1/2+\epsilon)\binom{s}{3}$ triples of one color (ar5iv.labs.arxiv.org/html/0901.3912, Introduction). The formal $F^{(t)}(n,\alpha)$ function and #161's exact wording are from Erdős's own [Er90b] ("Some of my favourite problems and results," 1990, p.21), quoted verbatim on erdosproblems.com/161: *"If I can hazard a guess completely unsupported by evidence, I am afraid that the jump occurs all in one step at $0$. It would be much more interesting if my conjecture would be wrong and perhaps there is some hope for this for $t>3$. I know nothing and offer \$500 to anybody who can clear up this mystery."* - Lower bound, all $t$, all $\alpha>0$ (erdosproblems.com/161, direct fetch): "results of Erdős and Spencer imply that $F^{(t)}(n,\alpha)\gg_\alpha(\log n)^{1/(t-1)}$ for all $\alpha>0$" — attributed to Erdős and Spencer's general probabilistic-discrepancy toolkit (most plausibly their book *Probabilistic Methods in Combinatorics*, Akadémiai Kiadó 1974, and/or "Imbalances in k-colorations," *Networks* 1 (1971/72), 379–385 — neither independently fetched here, flagged lower-confidence in provenance above), "and a similar upper bound holds for $\alpha$ close to $1/2$." - $t=2$ case fully settled up to the constant (erdosproblems.com/563, direct fetch): "It is easy to show via the probabilistic method that, for every $0\le\alpha<1/2$, $F(n,\alpha)\asymp_\alpha\log n$" — matching the general $(\log n)^{1/(t-1)}$ formula at $t=2$ (exponent $1$). The *exact* constant $c_\alpha$ in $F(n,\alpha)\sim c_\alpha\log n$ remains open. - $t=3$ fully resolved by Conlon, Fox, Sudakov, "Large almost monochromatic subsets in hypergraphs," arXiv:0901.3912 (*Israel J. Math.* 181 (2011), 423–432): for every fixed $\alpha>0$ (in fact for every fixed number of colors $\ell$), $F^{(3)}(n,\alpha)\ll_\alpha\sqrt{\log n}$. Combined with the Erdős–Spencer lower bound $(\log n)^{1/(t-1)}=(\log n)^{1/2}$ at $t=3$, this pins $F^{(3)}(n,\alpha)=\Theta_\alpha(\sqrt{\log n})$ for every fixed $\alpha\in(0,1/2)$ — a single order of magnitude, strictly below the tower-type $F^{(3)}(n,0)$ — proving there is exactly one jump, at $\alpha=0$, confirming Erdős's own guess for $t=3$. - $t\ge4$ genuinely open: only $F^{(t)}(n,\alpha)\gg_t(\log n)^{c_\alpha}$ is known (erdosproblems.com/161), with no matching upper bound of the CFS type — this is the live content of Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0?. - Structural obstruction to naive generalization: the companion paper Conlon–Fox–Sudakov, "Erdős–Hajnal-type theorems in hypergraphs," arXiv:1104.5544 (*JCTB* 102 (2012), 1142–1154), independently reproves the unconditional $\Theta(\sqrt{\log n})$ bound for all 3-uniform hypergraphs, but also proves that no analogous Erdős–Hajnal-type statement can hold for $k$-uniform hypergraphs with $k>3$ in the induced/$H$-free sense — a structural boundary that plausibly explains why $t\ge4$ has resisted the same technique (this wiki's Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? page documents this in more depth, including a forum-proposed "hypergraph Nikiforov" attack route for general $t$). - $\alpha=0$ endpoint: the Erdős–Hajnal–Rado conjecture (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)) implies $F^{(t)}(n,0)\asymp\log_{t-1}n$ — a tower-type ($(t-1)$-fold iterated logarithm) growth rate, in sharp qualitative contrast to the polynomial-in-$\log n$ growth for any fixed $\alpha>0$. This tower-vs-polynomial gap is the "jump" the problem asks about. - Relation to classical vertex-coloring discrepancy (notion A above) — same umbrella term, different object, worth not conflating: key results for context (Wikipedia, "Discrepancy of hypergraphs," WebFetch summary; cross-checked against independent WebSearch snippets on Spencer's theorem, Beck–Fiala, and Banaszczyk): - General probabilistic bound: for any $H$ on $n$ vertices, $m$ edges, $\mathrm{disc}(H)\le\sqrt{2n\ln(2m)}$ — random $\pm1$ vertex-coloring + Chernoff + union bound over the $m$ edges (the direct structural analogue of the $F^{(t)}$ upper-bound mechanism below, but with vertices colored instead of edges). - Spencer's "Six Standard Deviations Suffice" (1985): for $m\approx n$ (as many edges as vertices), $\mathrm{disc}(H)\le6\sqrt n$ — beating the $O(\sqrt{n\log n})$ random-coloring bound by removing the $\log$ factor, via a non-probabilistic partial-coloring/entropy-counting existence argument (too many roughly-balanced $\pm1$-vectors for too few "bad" linear-threshold hyperplanes to trap them all). Considered one of the milestones of discrepancy theory. - Beck–Fiala theorem: any hypergraph where each vertex lies in $\le t$ edges (max degree $t$) has $\mathrm{disc}(H)<2t$ — proved via an LP/linear-algebraic rounding argument. The Beck–Fiala conjecture that the optimal bound is $O(\sqrt t)$ remains open. - Banaszczyk's improvement: $\mathrm{disc}(H)=O(\sqrt{t\log n})$ via a convex-geometry/Gaussian-measure ("vector balancing") argument, closer to the conjectured $\sqrt t$. - Algorithmic note: Spencer's original six-deviations proof was non-constructive; Bansal (2010) gave an efficient SDP-relaxation-based rounding algorithm achieving the same $O(\sqrt n)$ bound constructively (arxiv.org/abs/1203.5747-adjacent literature, "Constructive Discrepancy Minimization by Walking on The Edges," Lovett–Meka and others, extends this further).

Technique

WHEN it applies: reach for the $F^{(t)}(n,\alpha)$ machinery whenever a problem asks *"for every large-enough subset of a colored/structured ground set, is the induced structure forced to be reasonably balanced (not too skewed to one class)"* — i.e. a relaxed, quasirandom-flavored Ramsey question strictly between full Ramsey (want literally *no* monochromatic substructure, $\alpha=0$, typically tower-type answers) and pure balance/quasirandomness (want *every* subset almost exactly $50/50$, $\alpha\to1/2$, typically easy log-type answers). The live research value is in the fixed, non-extreme $\alpha$ regime for $t\ge4$: does relaxing "monochromatic-free" to "merely $\alpha$-imbalanced-free" already knock a tower-type Ramsey bound down to a polynomial-in-$\log n$ bound, the way it provably does for $t=2,3$?

WHY it works — the two-sided mechanism

1. Upper-bound / construction direction (exhibiting a good coloring, giving $F^{(t)}(n,\alpha)\le\cdots$): take a uniformly random 2-coloring of the $\binom nt$ hyperedges. For a fixed $X$ of size $m$, the number of edges of each colour induced in $X$ is $\mathrm{Binomial}\!\big(\binom mt,\tfrac12\big)$-distributed; a Chernoff bound gives $\Pr[X\text{ is more than }\alpha\text{-imbalanced}]\le\exp(-c(\alpha)\binom mt)$. Union-bounding over the $\binom nm\approx(en/m)^m$ choices of $X$, the total failure probability is driven below $1$ once $\binom mt\gtrsim m\log(n/m)$, i.e. once $m^{t-1}\gtrsim\log n$ — this is exactly where the $(\log n)^{1/(t-1)}$ exponent comes from. This is the standard "random object + first-moment/union-bound repair" template (see 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), specialized here to edge- rather than vertex-colorings. It directly explains the achievable order of $F^{(t)}(n,\alpha)$ for $\alpha$ close to $1/2$; reaching *every* fixed $\alpha\in(0,1/2)$ with this exponent (as CFS did for $t=3$) requires more than the naive random-coloring bound and instead an iterative, partially-deterministic construction (see point 3 below). 2. Lower-bound / impossibility direction (no coloring can do better, giving $F^{(t)}(n,\alpha)\ge\cdots$ for every fixed $\alpha>0$): a Ramsey-type greedy majority-stepping-up argument, in the spirit of the classical Erdős–Szekeres-style recursive Ramsey-number lower bounds — repeatedly pick a new vertex and restrict the remaining candidate pool to whichever "color-majority" sub-pool it induces; each step shrinks the pool by a controlled (geometric-type) factor governed by the $t$-uniform structure, and the process can be pushed for roughly $(\log n)^{1/(t-1)}$ steps before the pool is exhausted. The subset built this way is, by construction, more than $\alpha$-imbalanced — showing that every 2-coloring, however cleverly chosen, must contain such a bad subset, hence $F^{(t)}(n,\alpha)$ cannot be smaller than this order (this reconstruction is consistent with the Erdős–Hajnal quoted result above but was not independently verified against a primary proof text — flagged in provenance).

HOW to use it to prove things (recombination steps for a solver)

1. Recast the target question as a 2-colored complete $t$-uniform hypergraph balance problem: ground set = the objects, the two colors = the two classes you want spread across every large-enough subset. 2. Locate your regime on the $\alpha$ axis. Near $\alpha=0$: this is Ramsey theory proper — expect tower-type answers, and look to the Erdős–Hajnal–Rado machinery (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)) and nibble/covering-style hypergraph techniques (Pippenger–Spencer hypergraph covering theorem (and the FGKMT generalization)). Near $\alpha=1/2$: the plain random-coloring Chernoff/union-bound recipe (mechanism 1 above) usually suffices directly. Fixed $\alpha\in(0,1/2)$, $t\ge4$ is the open frontier — this is exactly Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0?. 3. For an upper bound at fixed $\alpha$ beyond what the naive random-coloring argument reaches, follow the Conlon–Fox–Sudakov $t=3$ template (arXiv:0901.3912): iteratively build disjoint vertex-subsets across several rounds via Kővári–Sós–Turán-type dense-bipartite-subgraph extraction (not dependent random choice — CFS note their proof uses an iterative pigeonhole/bipartite-extraction construction, contrast their companion papers arXiv:0808.3760/arXiv:1104.5544 which do use 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 for the closely related hypergraph-Ramsey-number problem), shrinking the candidate pool by a controlled factor each round until reaching size $\Theta(\sqrt{\log n})$. 4. For a lower bound, use the greedy majority-stepping-up pigeonhole construction (mechanism 2 above) directly — it is comparatively cheap to adapt to new settings since it only needs a majority-color argument at each step, not a delicate probabilistic calculation. 5. Before attempting to generalize the $t=3$ upper-bound technique to $t\ge4$, check for structural obstructions first: Conlon–Fox–Sudakov's own arXiv:1104.5544 proves the natural Erdős–Hajnal-style generalization (in the induced/$H$-free sense) fails outright for $k$-uniform hypergraphs with $k>3$ — a documented cautionary result worth checking against before assuming the $t=3$ machinery "obviously" extends. 6. Do not conflate this with classical vertex-coloring hypergraph discrepancy (notion A above): if your problem instead asks to color *vertices* so that every *hyperedge* is balanced (rather than color edges so that every vertex-subset is balanced), the relevant toolkit is Beck–Fiala / Spencer's six-deviations / Banaszczyk's vector-balancing / Bansal's algorithmic SDP rounding — a different (though philosophically related, same probabilistic-method ancestry) machinery.

Related

- Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? — the \$500 open problem this function is defined for: does $F^{(t)}(n,\alpha)$ jump only at $\alpha=0$, for every $t$? Resolved for $t=3$ (single jump, confirmed); open for $t\ge4$. - Erdős #563 — the graph (t=2) discrepancy-Ramsey function F(n,α) has order Θ_α(log n) — the $t=2$ (graph) sibling: $F(n,\alpha)\asymp_\alpha\log n$ known via the probabilistic method; the exact constant $c_\alpha$ remains 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, giving the tower-type $\alpha=0$ endpoint that the "jump" is measured against. - 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 common-neighborhood technique family used in Conlon–Fox–Sudakov's broader hypergraph-Ramsey program (arXiv:0808.3760, arXiv:1104.5544); notably the specific $t=3$ discrepancy proof (arXiv:0901.3912) instead uses an iterative Kővári–Sós–Turán-type construction, a related but distinct mechanism. - 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 "random object + union-bound repair" template that the $F^{(t)}(n,\alpha)$ upper-bound Chernoff argument specializes (edges rather than vertices/elements are colored here). - Pippenger–Spencer hypergraph covering theorem (and the FGKMT generalization) — a sibling probabilistic-hypergraph existence machinery (Rödl nibble / Pippenger–Spencer / FGKMT) for a *different* covering/packing flavor of hypergraph problem; useful contrast for what nibble-type staged-random methods do and don't supply here (they are not the tool used for either direction of the $F^{(t)}$ bounds above). - Classical vertex-coloring hypergraph discrepancy (Beck–Fiala theorem and open conjecture, Spencer's "six standard deviations suffice," Banaszczyk's $O(\sqrt{t\log n})$ bound, Bansal's algorithmic SDP rounding) — same "hypergraph discrepancy" umbrella name but a genuinely different (vertex- not edge-coloring) object; documented here in ## Facts for contrast but flagged as a natural separate concept page not yet written in this wiki, since it is the more commonly-meant sense of "hypergraph discrepancy" in the discrepancy-theory literature at large (Chazelle's *The Discrepancy Method*, Matoušek's *Geometric Discrepancy* are the standard textbook references, not independently fetched this session).