Intervals of hypergraph Turán densities
Xizhi Liu, Oleg Pikhurko · 2026
Read Intervals of hypergraph Turán densities by Xizhi Liu, Oleg Pikhurko (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25914.txt.
Introduction
Liu and Pikhurko prove Turán densities for hypergraphs contain genuine intervals. A Turán density caps how dense a family can be while dodging banned patterns. For uniformity three or more, the density set holds a real interval reaching one. That settles a question posed in 2007 by Frankl and co-authors. It also shows the density set has Hausdorff dimension one, the largest possible. That settles a 2016 question of Grosu, who had not known if it was even nonzero.
Catalog record
| CREATOR | Xizhi Liu, Oleg Pikhurko |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 682541 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.25914
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Intervals of hypergraph Turán densities Xizhi Liu, Oleg Pikhurko Abstract We prove that, for every integer r ≥ 3 r\geq 3 , the set Π ∞ ( r ) \Pi^{(r)}_{\infty} of Turán densities of (possibly infinite) families of r r -graphs contains non-degenerate intervals, including an interval of the form [ 1 − δ r , 1 ] [1-\delta_{r},1] for some δ r > 0 \delta_{r}>0 . This answers a question of Frankl, Peng, Rödl and Talbot from 2007. This also shows that the Hausdorff dimension of Π ∞ ( r ) \Pi^{(r)}_{\infty} has the maximum possible value 1, thus resolving a question of Grosu from 2016, whereas previously it was not even known whether it is non-zero. We also derive that the set of uniform Turán densities of finite families of 3 3 -graphs is dense in a non-degenerate interval. 1 Introduction Given an integer r\geq 2 , an r -uniform hypergraph, or simply an r -graph, is a collection of r -subsets of a vertex set. For a hypergraph H , let V(H) denote its vertex set, and write v(H)\coloneqq|V(H)| for its number of vertices. We identify a hypergraph with its edge set, and hence write |H| for the number of edges of H . Given a family \mathcal{F} of r -graphs, let \ex(n,\mathcal{F}) be the maximum number of edges in an \mathcal{F} -free r -graph on n vertices. The Turán density of \mathcal{F} is \pi(\mathcal{F})\coloneqq\lim_{n\to\infty}{\ex(n,\mathcal{F})}/{\tbinom{n}{r}}. The existence of this limit follows from the averaging argument of Katona, Nemetz and Simonovits [ 21 ] . Let \Pi^{(r)}_{\mathrm{fin}} denote the set of Turán densities of finite families of r -graphs, and let \Pi^{(r)}_{\infty} denote the corresponding set when the forbidden family is allowed to be infinite. We allow \mathcal{F} to be empty, and hence 1\in\Pi^{(r)}_{\mathrm{fin}} . For graphs, the seminal Erdős–Stone–Simonovits theorem [ 12 , 10 ] determines all possible Turán densities: \Pi^{(2)}_{\mathrm{fin}}=\Pi^{(2)}_{\infty}=\{1-1/k\colon k\in\mathbb{N},\ k\geq 1\}\cup\{1\}. For r\geq 3 , determining \pi(\mathcal{F}) for a given family \mathcal{F} is notoriously hard in general. This problem, for example, for the complete \ell -vertex r -graph K_{\ell}^{(r)} , raised in [ 49 ] , remains wide open. In fact, the \$500 reward of Erdős, see e.g. [ 8 ] , for determining \pi(K_{\ell}^{(r)}) in at least one case with \ell>r\geq 3 is still unclaimed. For more background on hypergraph Turán problems, see the surveys of Füredi [ 15 ] , Sidorenko [ 48 ] , and Keevash [ 22 ] . The study of the algebraic and topological properties of the sets \Pi^{(r)}_{\mathrm{fin}} and \Pi^{(r)}_{\infty} for r\geq 3 goes back to the classical work of Erdős [ 9 ] . We call a number \alpha\in[0,1) a jump for r -graphs if there is a constant c>0 such that \Pi^{(r)}_{\infty}\cap(\alpha,\alpha+c)=\emptyset . Otherwise, we call \alpha a non-jump . In [ 9 ] Erdős proved that \Pi^{(r)}_{\infty}\cap(0,r!/r^{r})=\emptyset for every r\geq 3 and asked whether every number is a jump. This became one of his famous \$1000 problems. Frankl and Rödl [ 14 ] famously disproved this by proving the existence of non-jumps for every r\geq 3 . The topological viewpoint on possible Turán densities was developed by the second author in [ 38 ] , where it was proved that \Pi^{(r)}_{\infty}=\overline{\Pi^{(r)}_{\mathrm{fin}}} (in particular, \Pi^{(r)}_{\infty} is closed) and that \Pi^{(r)}_{\infty} has cardinality continuum for every r\geq 3 . On the algebraic side, for some time it was open whether \Pi^{(r)}_{\mathrm{fin}} could contain an irrational number; see the conjecture of Chung and Graham [ 6 , p. 95] . Such examples were independently found by Baber and Talbot [ 3 ] and by the second author [ 38 ] . Grosu [ 19 ] did a systematic study of algebraic properties of \Pi^{(r)}_{\mathrm{fin}} and \Pi^{(r)}_{\infty} and asked whether, for some r\geq 3 , the set \Pi^{(r)}_{\mathrm{fin}} contains an algebraic number of degree greater than r-1 . This was answered in a strong form by the authors [ 26 ] , who showed that, for every r\geq 3 and every integer d , the set \Pi^{(r)}_{\mathrm{fin}} contains a number of algebraic degree at least d . Further work on gaps in \Pi_{\infty}^{(3)} includes Baber and Talbot’s flag algebra proof of explicit jumps in \Pi^{(3)}_{\infty} [ 2 ] , based on Razborov’s method [ 40 ] and a criterion of Frankl and Rödl; see also [ 5 , 39 ] . Codegree and \ell -degree versions of Turán density were studied by Mubayi and Zhao [ 31 ] and by Lo and Markström [ 27 ] ; in that setting, the set of densities was shown to form a dense set in [0,1] . The multigraph analogue of the jumping constant conjecture was studied by Rödl and Sidorenko [ 45 ] . Further work on higher-uniformity non-jumps and jumping densities includes e.g. [ 34 , 37 , 36 , 35 , 20 ] . Despite extensive study of possible Turán densities, the fundamental question of whether \Pi^{(r)}_{\infty} contains any interval of positive length for r\geq 3 remained open. More specifically, Frankl, Peng, Rödl and Talbot [ 13 , Question 6.1] asked whether, for every r\geq 3 , there is \alpha_{r}<1 such that the whole terminal interval [\alpha_{r},1] lies in \Pi^{(r)}_{\infty} . Grosu [ 19 , Problem 5] asked to determine the Hausdorff dimension of \Pi^{(r)}_{\infty} or even just to prove that it is non-zero. Our main result settles these questions. In particular, it proves that, for every uniformity r\geq 3 , the set of possible Turán densities contains a terminal interval. Consequently, \Pi^{(r)}_{\infty} has positive Lebesgue measure, and has Hausdorff dimension 1 . Theorem 1.1 . For every integer r\geq 3 , there exists \delta_{r}>0 such that [1-\delta_{r},1]\subseteq\Pi^{(r)}_{\infty} . Although Theorem 1.1 is stated qualitatively, our proof is quantitative in principle: for each fixed r , it gives an explicit positive value of \delta_{r} once all auxiliary parameters are chosen explicitly. We make no attempt to optimize this value. In particular, the need to take a sufficiently far tail of primes in a fixed arithmetic progression, using explicit estimates for primes in arithmetic progressions such as those in [ 4 ] , causes a large loss, so the resulting \delta_{r} is very small. We discuss this further in Section 6 . We briefly indicate the main ingredients of the proof of Theorem 1.1 . First, we construct a slowly convergent sequence of finite 3 -graphs P_{i} whose Lagrangians approach a limit \alpha from above, with successive gaps to the limit asymptotically equal (Theorem 3.1 ). This sequence is built from a 3 -partite spectral gadget arising from the Ramanujan regular graphs constructed by Lubotzky–Phillips–Sarnak (LPS), with the properties used by us being summarised in Theorem 2.5 . We then incorporate it into a recursive construction of possible Turán densities (Section 4 ). The near equality of the successive gaps makes the recursive tails overlap, and an infinite subsequence can be chosen so as to approximate any prescribed real number in a non-degenerate interval. This fills an interval of densities in uniformity 3 . Finally, a standard complete join operation moves such an interval to a terminal interval near 1 , and a standard lifting argument transfers the result to every uniformity r\geq 3 . There is a parallel