A counterexample to Erdős Problem 1075

Abstract

Erdős asked whether, for every fixed r ≥ 3, there is a constant cr > r−r such that, for every ε > 0, every sufficiently large r-uniform hypergraph on N vertices with at least (1+ε)(N/r)r edges contains a subgraph on m → ∞ vertices with at least crmr edges. We give counterexamples for every r ≥ 16. The base construction is a sequence of explicit 16-uniform hypergraphs Gn whose unnormalized Lagrangians satisfy 16−16(1 + 1/(4(14n)14)) ≤ λ(Gn) ≤ 16−16 + 1/(15! n). Blow-ups give the counterexample for r = 16, and adjoining common vertices to every edge lifts it to all larger uniformities. Thus Problem 1075, as a statement for all r ≥ 3, has a negative answer. The endpoint question remains open for 3 ≤ r ≤ 15, including the case 2/9 for 3-graphs. Concretely: for every γ > r−r there are ε > 0 and arbitrarily large r-uniform hypergraphs H with e(H) ≥ (1+ε)(v(H)/r)r and e(H[S]) < γ|S|r for every nonempty S ⊆ V(H) — a conclusion stronger than the formulation of the problem. Context. With the usual density normalization the threshold (N/r)r corresponds to αr = r!/rr, and Erdős proved that every number in [0, αr) is a jump for r-graphs; Problem 1075 is the endpoint question at αr. Frankl and Rödl disproved the earlier jumping constant conjecture; Frankl, Peng, Rödl and Talbot showed (5/2)r!/rr is a non-jump; Peng gave the lifting theorem to larger uniformities; Yan and Peng brought this to (54/25)r!/rr. Shaw recently proved that 2r!/rr is a non-jump for r ≥ 4 and that no smaller non-jump follows from his finite-pattern formulation of the Frankl–Rödl method; Liu and Mubayi then proved 4/9 is a non-jump for 3-graphs by a construction outside that framework. The construction here is likewise not an instance of Shaw's finite-pattern criterion, since its distinguished links follow a matching and a shifted matching around a cycle and the proof controls the full Lagrangian of a growing sequence, so Shaw's Theorem 4.3 does not apply. Status. Preprint, not yet refereed. As of 5 September 2026, Erdős Problem 1075 is listed as open on erdosproblems.com, with no proof claims submitted. Declaration of generative AI and AI-assisted technologies. GPT-6 Astra was used to generate the mathematical proofs and draft the manuscript. GPT-5.6 Sol and Claude Opus 5 were used only for editorial review of the exposition. GPT-6 Astra was run in a research environment containing earlier results produced by GPT-5.6 Sol and Claude Opus 5, but those earlier results did not contribute to the final mathematical arguments. The author reviewed the final manuscript and takes full responsibility for its content.