Turing universality, computability, and incompleteness in hypergraph Turán theory
Given a finite family $\mathcal F$ of forbidden $r$-graphs, the Turán problem asks for the maximum asymptotic edge density of $\mathcal F$-free $r$-graphs and the structure of near-extremal examples. We show that both questions can encode arbitrary computation. Fix a universal Turing machine $\mathsf U$. For every sufficiently large fixed $r$, there is a rational $τ_r\in(0,1)$ such that, from each binary word $β$, one can construct a finite family $\mathcal F_{r,β}$ with $π(\mathcal F_{r,β})=τ_r$ if $\mathsf U$ does not halt on $β$, and $π(\mathcal F_{r,β})>τ_r$ otherwise. The same dichotomy…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.04295
curl -X POST /api/v1/records/arxiv/2609.04295/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.04295/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'