{"id":"arxiv/2609.04295","url":"https://arxiv.org/abs/2609.04295","tags":["math.CO","math.LO"],"score":0,"title":"Turing universality, computability, and incompleteness in hypergraph Turán theory","domain":"math.CO","source":"arxiv","authors":["Heng Li","Xizhi Liu"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-03","reactions":{}}