no. 14 · Friday 13 November 2026
Turing universality, computability, and incompleteness in hypergraph Turán theory
Abstract
The hypergraph Turán problem asks for the maximum asymptotic edge density of hypergraphs avoiding a forbidden family and the structure of near-extremizers. We prove that both encode arbitrary computation. Fix a universal Turing machine $\mathsf{U}$. For each fixed $r\ge3$, there is a rational $τ_r\in(0,1)$ and an effective map from binary words $β$ to finite families $\mathcal{F}_{r,β}$ of $r$-graphs such that $π(\mathcal{F}_{r,β})=τ_r$ if $\mathsf{U}$ does not halt on $β$, and $π(\mathcal{F}_{r,β})>τ_r$ otherwise. For $r=3$, a single forbidden $3$-graph $P_β$ suffices. For all sufficiently large fixed $r$, we construct finite families exhibiting a parallel structural dichotomy. Nonhalting gives a unique extremal limit and edit-distance stability around a fixed finite profile. Halting yields 2 nonempty compact phases with opposite signs of a continuous statistic depending only on $r$; each phase is homeomorphic to the full extremal limit space of $P_β$. Hence uniqueness, connectedness, and finite-profile stability are undecidable. Our ZFC-verifiable reductions also yield independence results for every consistent computably axiomatized extension of ZFC, even for single forbidden $3$-graphs. We further classify the complexity of exact density comparison, characterize densities attainable by effectively enumerated families, and establish Busy-Beaver growth of minimal witnesses and the absence of computable positive lower bounds on density gaps.
- comments
- proofs simplified; improved main result from finite family of r-graph to single 3-graph
- fields
- Combinatorics, Logic