Determine $A_3$, the set of jump densities for $3$-uniform hypergraphs (Erdős–Simonovits) (Erdős #837)
Statement
For $k\geq 2$, let $A_k\subseteq[0,1]$ be the set of $\alpha$ for which there exists some $\beta(\alpha)>\alpha$ with the following property: whenever $G_1,G_2,\ldots$ is a sequence of $k$-uniform hypergraphs with $$\liminf_{n}\frac{e(G_n)}{\binom{\lvert G_n\rvert}{k}}>\alpha,$$ there exist subgraphs $H_n\subseteq G_n$ with $\lvert H_n\rvert\to\infty$ and $$\liminf_{n}\frac{e(H_n)}{\binom{\lvert H_n\rvert}{k}}>\beta,$$ and moreover this property fails if the strict inequality $>\alpha$ is replaced by $\geq\alpha$. (Here $e(\cdot)$ is the number of edges and $\lvert\cdot\rvert$ the number of vertices.) Determine the set $A_3$.
Acceptance. FULLY RESOLVES: a complete and correct determination of the set $A_3$ — an explicit description together with a proof that it consists of exactly those $\alpha$ (machine-checkable preferred, otherwise a full written proof). ADVANCES (each independently checkable): (a) prove that a specific value $\alpha$ belongs to $A_3$ or does not (a newly certified jump or non-jump for $3$-uniform hypergraphs), with proof or a verifiable Lagrangian certificate; (b) determine $A_3$ restricted to a stated subinterval of $[0,1]$; or (c) a reproducible computation certifying new non-jump values, with the code and the numerical certificate. Deliver the proof, or the certified value(s) with the accompanying computation.
Background
A problem of Erdős and Simonovits [Er74d]; listed as open on erdosproblems.com/837 (fetched 2026-07-13, status 'open', tagged 'graph theory | hypergraphs'). Terminology: a value $\alpha$ is called a jump for $k$-uniform hypergraphs when such a $\beta>\alpha$ exists, meaning edge density exceeding $\alpha$ forces arbitrarily large subgraphs of density bounded away above $\alpha$; the set $A_k$ isolates the threshold values where the jump property holds just above $\alpha$ but not at $\alpha$. For ordinary graphs ($k=2$) the Erdős–Stone–Simonovits theorem pins these threshold points down completely, and it is known that $$A_2=\left\{1-\tfrac1k:k\geq 1\right\}$$ — exactly the Turán densities. For $k\geq 3$ the situation is genuinely different: Frankl and Rödl (1984) showed that hypergraphs do not jump everywhere — there exist explicit values of $\alpha$ that are not jumps for $3$-uniform hypergraphs — disproving the natural analogue of the graph result. Consequently $A_3$ is a proper subset of the picture that $A_2$ suggests, and it has not been determined; even deciding whether a given specific value lies in $A_3$ is hard. No Erdős prize is attached to this problem on the source page. Attacker's tool: Lagrangian-based numerical computation of hypergraph densities to certify specific values as jumps or non-jumps (Frankl–Rödl-type blow-up constructions plateaus), progressively narrowing $A_3$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #837 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.