Jumps and non-jumps of hypergraph Turán densities (Erdős's jumping constant conjecture, disproved by Frankl–Rödl)

Statement

For an integer $r\ge 2$, the Turán density $\pi(\mathcal F)$ of a family $\mathcal F$ of $r$-uniform hypergraphs ($r$-graphs) is the limiting maximum edge density of an $n$-vertex $r$-graph containing no member of $\mathcal F$ as a subgraph, as $n\to\infty$. Let $\Pi_\infty(r)\subset[0,1)$ be the set of all values $\pi(\mathcal F)$ realizable this way (over all finite families $\mathcal F$).

Definition (jump). $\alpha\in[0,1)$ is a jump for $r$ if there exists $c(\alpha)>0$ such that: for all $\epsilon>0$ and all $t\ge1$, there is $n_0=n_0(\alpha,\epsilon,t)$ such that every $r$-graph on $n\ge n_0$ vertices with edge density $\ge\alpha+\epsilon$ contains a subgraph on $t$ vertices with edge density $\ge\alpha+c$. Equivalently (Pikhurko's $\Pi_\infty$ formalization, arXiv:1204.4423): $\alpha$ is a jump iff $\Pi_\infty(r)\cap(\alpha,\alpha+\epsilon)=\varnothing$ for some $\epsilon>0$ — i.e. no finite forbidden family can have its Turán density land in a small interval strictly above $\alpha$. A non-jump is an $\alpha$ for which this fails: densities arbitrarily close to (but above) $\alpha$ are achievable by $\alpha$-free-ish families whose extremal density sits right at $\alpha+o(1)$ without a forced gap.

Erdős–Stone–Simonovits (the $r=2$/graph case, for contrast). For ordinary graphs, every $\alpha\in[0,1)$ is a jump — this is an immediate corollary of the Erdős–Stone–Simonovits theorem (every graph Turán density is of the form $1-1/(k-1)$, a discrete, well-ordered set with no accumulation points below $1$).

Erdős's theorem (1971). For all $r\ge3$, every $\alpha\in[0,\,r!/r^r)$ is a jump (Erdős, "On some extremal problems on $r$-graphs," *Discrete Math.* 1 (1971), 1–6). Here $r!/r^r$ is exactly the Lagrangian of the single-edge $r$-graph (the density achieved by the uniform weighting on $r$ points), so this says: below the density of "just one balanced edge's worth of Lagrangian mass," the jump phenomenon always holds, by the same supersaturation mechanism that proves it for graphs.

Erdős's jumping constant conjecture. For all $r\ge3$, every $\alpha\in[0,1)$ is a jump — i.e. the graph-case phenomenon (no accumulation of achievable Turán densities anywhere) was conjectured to extend verbatim to all uniformities.

**Disproved: Frankl–Rödl, "Hypergraphs do not jump," *Combinatorica* 4 (1984), 149–159. They exhibit an explicit infinite family of non-jumps: for every $r\ge3$ and every integer $l>2r$, $$ \alpha \;=\; 1-\frac{1}{l^{\,r-1}} $$ is a non-jump**. So the conjecture is false for every uniformity $r\ge3$ — there exist values arbitrarily close to $1$ where the Turán-density spectrum $\Pi_\infty(r)$ accumulates rather than jumps, in sharp contrast to the $r=2$ graph case (arXiv:1004.3733, Section 1; corroborated via ar5iv full-text extraction and independent WebSearch of the Frankl–Rödl citation).

Later refinement (Baber–Talbot, arXiv:1004.3733, using Razborov's flag-algebra method). The disproof leaves open exactly which $\alpha\in[r!/r^r,1)$ are jumps vs. non-jumps. Baber–Talbot proved the first jumps ever found strictly above Erdős's classical threshold $r!/r^r$ for any $r\ge3$: for $r=3$, every $\alpha\in[0.2299,\,0.2316)$ is a jump. Before this, "nothing was previously known regarding the location of jumps or non-jumps in the interval $[r!/r^r,\,5r!/2r^r)$ for any $r\ge3$" (their own framing, arXiv:1004.3733).

Facts

- The Frankl–Rödl reduction to Lagrangians is the structural heart of the whole area. Frankl–Rödl proved (as their Theorem 1.2, per the ar5iv extraction of arXiv:1004.3733) that $\alpha$ is a jump for $r$ iff $\alpha$ is the Turán density $\pi(\mathcal F)$ of some *finite* family $\mathcal F$ of $r$-graphs with $\min_{F\in\mathcal F}\lambda(F)>\alpha$, where $\lambda(F)$ is the Lagrangian of $F$ — the Motzkin–Straus-style quantity $\lambda(F)=\max\{\sum_{e\in E(F)}\prod_{i\in e}x_i : x_i\ge0,\ \sum_i x_i=1\}$ (Motzkin–Straus introduced the graph analogue in 1965 to reprove Turán's theorem; extended to $r$-graphs, it governs the density achievable by iterated blow-ups of $F$). This turns an analytic/asymptotic statement ("no density accumulates just above $\alpha$") into a purely combinatorial/algebraic search problem ("does some finite obstruction family with all-Lagrangians-above-$\alpha$ have Turán density exactly $\alpha$"). Erdős's single-edge $r!/r^r$ theorem is the degenerate case $\mathcal F=\{$single edge$\}$ of this reduction. - Known finite Turán densities for $r=3$ were extremely sparse for decades. Per arXiv:1204.4423 (Pikhurko), before Mubayi's 2006 result the only known members of the finite-family Turán-density set $\Pi_{\mathrm{fin}}(3)$ were $\{0,\,2/9,\,4/9,\,3/4,\,1\}$; Mubayi then exhibited the infinite family $(m-1)(m-2)/m^2\in\Pi_{\mathrm{fin}}(3)$ for every $m\ge4$ (accumulating at $1$, in the same qualitative spirit as the Frankl–Rödl non-jumps). - The conjecture's disproof is asymmetric: it kills the "always" claim but does not resolve the general classification. Frankl–Rödl's non-jump values $1-1/l^{r-1}$ ($l>2r$) sit near the top of $[0,1)$; Erdős's classical theorem covers the bottom interval $[0,r!/r^r)$; Baber–Talbot's flag-algebra jumps cover a further small window just above $r!/r^r$ for $r=3$. The overwhelming majority of $[0,1)$ for every $r\ge3$ is, as of the sources found here, not classified as jump or non-jump — this is an active, ongoing research program (recent arXiv titles found in this search alone: "Non-jumps of hypergraphs" (2511.07715), "The number 4/9 is a non-jump for 3-graphs" (2605.13567), "Generating non-jumps from a known one" (2208.00794), "Hypergraphs accumulate" (2405.08239), "Intervals of hypergraph Turán densities" (2605.25914) — titles/arXiv IDs from WebSearch result listings, abstracts not independently fetched for this page). - This is a distinct object from erdosproblems.com's #161 (already flagged on this wiki's own Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? page, written independently in this same session): #161's "jump" is about the two-colour hypergraph-discrepancy Ramsey function $F^{(t)}(n,\alpha)$ (does it increase continuously in $\alpha$, or jump — a Ramsey/discrepancy question); this page's "jump" is about the achievable-Turán-density spectrum $\Pi_\infty(r)$ (does it have gaps just above $\alpha$, or accumulate). Both trace to Erdős-era hypergraph extremal thinking and both use the word "jump," but they are formally unrelated statements about different functions.

Technique

WHY Erdős's theorem works below $r!/r^r$ (supersaturation). If an $n$-vertex $r$-graph has density $\ge\alpha+\epsilon$ for $\alpha<r!/r^r$, then it has *more* edges than the Turán-type extremal bound for excluding a single balanced edge-blowup pattern would allow at that density, forcing — via a counting/averaging (supersaturation) argument — many copies of a fixed small dense configuration; averaging over these copies produces some $t$-vertex subset with density strictly above $\alpha$ by a fixed gap $c(\alpha)$. This is exactly the graph-case Erdős–Stone–Simonovits mechanism, and it works whenever the target family is as simple as "a single edge," because a single edge's Lagrangian ($r!/r^r$) is the smallest possible nonzero Lagrangian any forbidden family could have — so *every* $\alpha$ below it is automatically below *every* candidate obstruction's Lagrangian, and the Frankl–Rödl reduction's hypothesis ($\min_F\lambda(F)>\alpha$) is satisfied trivially.

WHY the Frankl–Rödl construction produces non-jumps (iterated blow-up). To show a specific $\alpha=1-1/l^{r-1}$ is *not* a jump, Frankl–Rödl build, for every $\delta>0$, an $r$-graph family whose extremal (Turán) construction has density in $(\alpha,\alpha+\delta)$ with no forced gap above $\alpha$ — achieved by taking a small $r$-graph $H$ on $\approx l$ vertices tuned so that its iterated blow-up (replace each vertex by an independent set of size $m$, recursively) has limiting density that can be pushed arbitrarily close to $\alpha$ from above while staying free of the forbidden configuration, for a *sequence* of different forbidden families indexed increasingly finely — i.e., they engineer the Turán-density spectrum $\Pi_\infty(r)$ itself to *accumulate* at $\alpha$ from above rather than avoid a neighborhood of it. This directly falsifies the Frankl–Rödl-reduction hypothesis "$\exists$ finite $\mathcal F$ with $\pi(\mathcal F)=\alpha$ and $\min_F\lambda(F)>\alpha$" at that specific $\alpha$: any such family's Lagrangian gets caught arbitrarily close to $\alpha$ too, so the gap $c(\alpha)$ required by the jump definition cannot exist.

HOW to use this technique family to prove things (recombination steps)

1. To prove $\alpha$ IS a jump, by the Frankl–Rödl reduction it suffices to exhibit *any* finite family $\mathcal F$ of $r$-graphs with $\pi(\mathcal F)\le\alpha$ (via a genuine Turán-type extremal upper-bound proof, e.g. flag algebras) and $\min_{F\in\mathcal F}\lambda(F)>\alpha$ (a finite Lagrangian computation, often itself via flag algebras / semidefinite programming — this is exactly the Baber–Talbot route for $[0.2299,0.2316)$: they found $\mathcal F'=\{F_1,\dots,F_5\}$ with $\pi(\mathcal F')\le0.2299$ computed via Razborov's flag-algebra SDP method over 7-vertex $\mathcal F'$-free $3$-graphs, while $\min_i\lambda(F_i)\approx0.2316$). 2. To prove $\alpha$ is a NON-jump, construct an explicit (iterated blow-up or similar recursive) $r$-graph family whose Turán density can be pushed arbitrarily close to $\alpha$ from above without a gap — i.e., directly falsify the jump definition by exhibiting $\Pi_\infty(r)$-elements in every neighborhood $(\alpha,\alpha+\epsilon)$. This is a pure existence/construction task, not an extremal-bound-proof task, and is the route used both by the original Frankl–Rödl $1-1/l^{r-1}$ family and by later "generating non-jumps from a known one" style results (arXiv:2208.00794 — title only, not independently verified in this search) that bootstrap new non-jumps from previously-known ones. 3. WHEN this technique family applies: any question of the shape "does the set of achievable extremal densities for [some combinatorial structure]-free configurations have gaps, or does it accumulate?" — the Lagrangian/blow-up machinery here is specific to *hypergraph Turán densities*, but the jump-vs-accumulate dichotomy and the two-sided proof recipe (finite-family-with-Lagrangian-gap for jumps; iterated-blow-up-density-approximation for non-jumps) is the reusable pattern. 4. Current frontier / where derivation is still open: the overwhelming majority of $\alpha\in[0,1)$ for $r\ge3$ remains unclassified as jump or non-jump (see Facts above); any new finite family with a computable Lagrangian gap (jump direction) or any new iterated-construction density-accumulation argument (non-jump direction) is a direct, well-defined contribution to filling in $\Pi_\infty(r)$'s known structure.

Related

- Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? — terminologically adjacent but distinct: Erdős #161 is about the hypergraph discrepancy-Ramsey jump function $F^{(t)}(n,\alpha)$, not the Turán-density spectrum $\Pi_\infty(r)$ this page concerns; already flagged from both directions to prevent conflation. - Finite-field / projective-plane constructions for extremal additive sets — a different "explicit algebraic/combinatorial construction beats a naive bound" technique family in extremal combinatorics; contrasts with the iterated-blow-up constructions used here for non-jumps, which are recursive/self-similar rather than algebraic. - Concept referenced but not yet its own page: "Lagrangian of a hypergraph" / "Motzkin–Straus theorem for hypergraphs" (the $\lambda(F)$ machinery that is the technical hinge of the entire Frankl–Rödl reduction and every jump/non-jump proof since) and "flag algebra method" (Razborov's SDP-based technique, used by Baber–Talbot to compute both sides — $\pi(\mathcal F)$ and $\lambda(F_i)$ — of the jump criterion for $r=3$) — both flagged here as natural next concept pages this wiki should add, since they are the actual proof engines behind every result on this page.