WorksMathematics
The Turán density of the tight five-cycle
Abstract
The tight five-cycle is the three-uniform hypergraph whose edges are the five cyclically consecutive triples on five distinct vertices. We prove that its Turán density is . This answers the conjecture usually attributed to Mubayi and Rödl, explicitly stated by Mubayi, Pikhurko and Sudakov. Mubayi and Rödl's recursive construction gives the lower bound. The upper bound follows the reduction of Bodnár, León, Liu and Pikhurko, whose theorem concerns forbidding both the tight four-cycle and the tight five-cycle, or a tight cycle of length at least seven not divisible by three. We establish the two estimates needed for the five-cycle alone by exact rational certificates, using weighted link inequalities to include configurations containing a complete four-vertex hypergraph. We give the finite counting argument that turns the certificates into these estimates and then into the density bound. The whole proof, including this counting argument, is checked in Lean; its finite computations run as compiled code, so the check trusts Lean's compiler as well as its kernel. This work has not yet been reviewed by experts. The proofs, the Lean formalization and the text were produced by AI models, working under the author's direction.
Introduction
A three-uniform hypergraph, or 3-graph, on is a subset of . Put
A copy in means an injective map with for every ; extra edges are allowed. Write for the largest number of edges in a -free 3-graph on vertices, and .
Theorem 1. The injective, non-induced tight five-cycle has Turán density
Precisely, for every real there is an integer such that for every integer ,
Mubayi–Rödl’s Construction 1 gives the lower bound [2 Construction 1]1; the equality is stated explicitly by Mubayi, Pikhurko and Sudakov [3 §2.4, Conjecture 7]. They also record Razborov’s earlier upper bound [3, 20 §2.4]. In prior work posted on October 24, 2026, Lidický and Volec obtained the numerical flag-algebra upper bound (and 0.46507 by their cutting-plane linear-programming method) [18 §6]. It bounds the same density from above; the value proved here lies below it. Their method and computations are not used here. The usual attribution is recorded in Kamčev–Letzter–Pokrovskiy [4 Conjecture 1.1]; their Theorem 1.3 gives the equality for all sufficiently large cycle lengths not divisible by three. Bodnár–León–Liu–Pikhurko (BLLP) prove the equality for and for with and [5 Theorem 1.1].
Falgas-Ravry and Vaughan establish the sharp bound for 3-graphs whose edges are the triples inducing a directed out-star in a digraph [7 §3.1, Proposition 25 and Theorem 27]. Huang gives an analytic proof of the directed-star result [8 §§2 and 4]. This restricted class does not include every -free 3-graph.
The partition method and reduction are BLLP’s [5 Propositions 3.2–3.3, Lemma 4.1 and the proof of Theorem 2.4]. Here their two estimates are established for alone, with the precise hypotheses below. The difficult step is the estimate for bad edges minus missing triples when is allowed: BLLP identify this obstacle in [5 §7]. The additional link inequalities below permit exact certificates over all -free six-vertex configurations. The colored flag setup and degree and local-maximality rows follow BLLP’s supplementary calculations [6 notebook, zero-based code cells 1 and 4]. That notebook uses Bodnár’s SageMath framework, documented as FlagAlgebraToolbox [10 §§1.2 and 2.4]. Finite sampling makes the certificate-to-graph passage explicit. The proof depends on these computations and their Lean formalization; § 7 states the formal conclusion and its trust boundary. Earlier computations for alone include Xizhi Liu’s numerical flag-algebra optimization [12 edge-density objective and saved output]. The present argument supplies exact certificates and the finite estimates needed for the unrestricted upper bound.
Ferudun’s October 16, 2026 preprint [13 Theorems 1–3 and §5] optimizes the classical recursive construction by a logarithmic-state algorithm and determines its quadratic term. The recursive construction family is shared. Ferudun explicitly distinguishes this construction-side result from an upper bound for arbitrary -free hypergraphs. The Ulam.AI UnsolvedMath record AIM-COMBINATORICS-0153 reports an exact deficit identity, weighted stability and an optimized finite recurrence within the same recursive family [14]. That summary also leaves the unrestricted upper bound open; its underlying proof was not read or checked here.
For the related cycle with one edge deleted, Balogh and Luo [16] determine the density for all sufficiently long lengths not divisible by three. Bodnár, León, Liu and Pikhurko [15 Theorem 1.1] and, independently, Lidický, Mattes and Pfender [17 Abstract] determine density . That is a different forbidden hypergraph.
Two partition estimates
For let and define
A cut is locally maximal if for every . Thus a maximum cut is locally maximal. Write for vertex degree, and . The following are the -only counterparts of BLLP’s Propositions 3.2 and 3.3; they use binomial normalization, an asymptotic cut threshold, and coefficient one on the missing triples.
Proposition 2. For every real there exists an integer such that, for every integer and every -free 3-graph on vertices, implies .
Proposition 3. For every real there exist a real and an integer such that, for every integer , every -free 3-graph on vertices and every , the hypotheses
is locally maximal,
for all ,
,
imply .
These hypotheses are auxiliary estimates, not restrictions in Theorem 1. In particular, the same cut of an extremal graph will meet both estimates.
Certificates and finite sampling
The certificates use Razborov’s flag algebra method [19 §2] in the finite-sampling form described by BLLP [5 §3]. For , sample an ordered injection into . Write for the triple in edge indicators. If a cut is present, color its vertices by . Let be the probability of its induced six-vertex isomorphism class . For any function of the sample, let be its average over all orders of . Then
Only -free classes occur, including classes containing .
The link inequalities
Put and let indicate that spans . Put
Repeated vertices are permitted in the following sums; an edge always has three distinct vertices.
Lemma 4. If is -free, , and for every , then
Multiplication by and summation over gives the corresponding three-variable inequality. Dropping the last non-edge factor on the right gives a further valid inequality.
Proof. For fixed , , let and . If , both and are absent: otherwise respectively the orders and give a tight five-cycle. Consequently whenever . Symmetry and give
Terms of zero weight contribute zero; all denominators in a nonzero term are positive. This proves (2).
Fixing roots, restrict each free vertex by the same predicate on its edges to the roots and its color. Applying Lemma 4 with indicator weights gives the three-variable rows, with or without the last non-edge factor, and the two-variable rows. Nonnegative rational weights give the weighted two-variable rows. On passing to distinct samples the diagonal is removed, producing an error at most , or for two-variable weights bounded by . The diagonal is retained before this passage; it need not vanish on . Appendix § 8 gives the other finite errors.
The cut certificate
A selector has a specified edge or non-edge type on and a rational function assigning each possible three-edge pattern of an external vertex a probability in . Given the roots, put each other vertex in a set independently with that probability. Let be the probability of the root type, and let be the probability of that type together with and . On a class, and denote the averages of these same six-vertex integrands. Averaging the number of selected edges gives
Indeed, for every fixed root triple and every outcome , the selected edges avoiding the roots number at most ; each edge has six orders.
The rational certificate verifies, on every uncolored class,
Here , , and every is positive semidefinite. The matrices are products of rooted flag indicators; . The scalar rows are the link rows above and the two density products and its non-edge counterpart. All coefficients are averaged as in (1).
Proof of Proposition 2. Average (4) using (1). The finite errors in Appendix § 8, weighted by the fixed certificate coefficients, have total at most for all sufficiently large , where depends only on the certificate. Thus some selector satisfies for all sufficiently large . Since , its denominator is positive. Equation (3) now gives . Finally , proving the stated quantifiers.
The bad-minus-missing certificate
For a colored class set . The second rational certificate verifies, class by class,
Here are positive semidefinite, , and may have either sign. The rows express local maximality, cut density, edge density at , and the three-variable link inequality without the last non-edge factor. The rows express degree differences. Their explicit sampling functions are in Appendix A. Only the matrices and multipliers are divided by the certificate’s positive integer scale; is unscaled.
Proof of Proposition 3. Each triple occurs equally often in six-sets, so exactly. For hypotheses with slack , averaging (5) and using the finite errors gives
The absolute values of are used for degree-difference errors. The density and cut products have lower bounds , with , as defined in the appendix. All other errors are . Given , take and then so that and for every . The result follows from . □
Proof of the density theorem
Proof of Theorem 1. For the lower bound use Mubayi–Rödl’s construction [2 Construction 1]: partition into , take every triple with two vertices in and one in , and repeat inside (Figure 1). A pair shared by two edges determines their construction level, so all edges of a tight cycle would have the same level. Their three consecutive vertices would then have a periodic part pattern with two ’s and one , incompatible with length five [4 Example 1.2]. With , the limiting density is ; rounding and a finite-depth approximation give .
Figure 1. The recursive construction. The triangle illustrates an edge with two vertices in and one in ; all such triples are included.
For the upper bound let attain . Replacing a vertex by a clone of preserves -freeness: the collapsing map sends edges to edges, and every pair of vertices of lies in an edge, so any cycle image is still injective. Extremality therefore gives for all ; the possible loss is at most the codegree of . Choose a maximum cut , which is locally maximal, and set , . Since and , the lower bound, Proposition 2, and the degree inequality meet all the hypotheses of Proposition 3 on this same cut for sufficiently large . For each fixed we obtain
Indeed, the edges consist of the cut edges, the bad edges and the edges inside ; the cut edges number . We may use Proposition 2 with error at most . For large , , so . On the other hand , which rules out . Hence .
The scalar inequality in BLLP [5 Fact 2.9(i)] is
It follows from the factorization
Let . For every there is a constant such that for every integer . If , combine (6)–(7) and to obtain
for all sufficiently large . Taking a subsequence tending to the limsup and then letting tend to zero gives , a contradiction. Together with the lower bound this proves convergence and the theorem. □
Formal verification
The closed Lean theorem has the following name and type, with ℕ and ℝ denoting Lean’s natural and real number types:
TightCycleC5.Bridge.mubayi_rodl_checked :
Filter.Tendsto
(fun n : ℕ =>
(TightCycleC5.ex n : ℝ) / (n.choose 3 : ℝ))
Filter.atTop (nhds (2 * Real.sqrt 3 - 3))
Here TightCycleC5.ex n is the maximum edge count over all finite sets of three-element subsets of Fin n for which there is no injection with for every ; addition in Fin 5 is cyclic. Thus it is exactly from Theorem 1, with no induced-copy restriction or assumption on or its partitions. Total real division defines the initial terms for , which do not affect the limit.
The class-by-class certificate assertions (4) and (5), including positivity and class coverage, are checked in the formalization and by the published exact certificate checkers (linked below the title); they are not derived from a printed list of coefficients here. The written argument proves their passage to Propositions 2–3 and Theorem 1. The formal proof includes this passage and the density reduction. It depends on 692 native_decide facts, trusting Lean’s compiler and runtime as well as its kernel; it is not a kernel-only proof. These facts check finite arithmetic, table and coefficient comparisons, and two rational Gram identities. The class covers, arithmetic-range coverage, all six uncolored positive-semidefinite matrices and the other 36 colored matrices have kernel proofs.
The Lean bundle is published with the paper (linked below the title). Its checking material [1] specifies the pinned toolchain, all standard axioms, the exact 692-fact dependency list and reproduction commands. The recorded full replay checked the frozen mathematical sources; a later adapter check reused those validated dependencies and elaborated a fresh probe of the theorem’s exact type and allowed axioms. That probe is not a second replay. The original endpoint placeholder supplies only a type: its proof is outside the checked theorem’s dependency chain. The checking material distinguishes these executions from the standalone Lake build, which was not exercised.
For related formalization, Jeong, Park, Hyun, Oum and Yang [9, Abstract] formalize flag algebras for finite simple graphs. Jeong, Park, Im, Lee and Yang combine degree-stationarity with an exact seven-vertex certificate for the tetrahedron and formalize its bound [11 §§2.5 and 3]. The present development proves the finite sampling estimates for the 3-graphs and colored 3-graphs used here directly.
Finite sampling estimates
Here are the row definitions and estimates used in the two certificate arguments. They apply for and always to ordered injections; . A flag is the induced graph, its colors when present, and its designated ordered roots, with free vertices identified up to the specified permutations. Its indicator vector is one-hot; a coarsening of such a flag is also permitted.
Link rows. For roots , let . Choose a nonempty subset of its eight patterns, and optionally a set of allowed colors. Every one of satisfies the same restriction; a root-type indicator may also be imposed. The row is the right side minus the left side of the three-variable version of Lemma 4, with or without the last non-edge factor. Its average is at least : the removed diagonal has at most terms and the conditional denominator is . For the two-variable rows fix and use a common nonnegative weight on each free vertex determined by
If its maximum is , the diagonal weighs at most and the average is at least .
Positive semidefinite rows. For a fixed root tuple of a specified type, let be a one-hot flag vector and be positive semidefinite. Put . Summing all pairs of flags gives , where is the sum of their indicator vectors. Removing intersecting free sets gives respectively the lower bounds
For two roots there are intersecting pairs of ordered free pairs, and . For four roots only the diagonal pairs are removed.
Products on disjoint triples. For functions of ordered triples, , let denote their average on a uniformly sampled ordered triple of distinct vertices. Then
This follows by removing the pairs of triples that intersect, since . For cut rows use ; for density rows use . The multiplier is a three-vertex flag indicator (the edge and non-edge indicators in the uncolored certificate). Thus gives the lower bound when . The unconditional density row has lower bound exactly. In particular, ; a uniform bound uses a constant strictly larger than nine.
Local maximality and regularity. Put
For every one-root flag indicator , local maximality gives
For fixed , the unrestricted sum of over ordered is . The sum of over the free triple is nonnegative and independent of . Deleting triples meeting removes possibilities per fixed pair, giving the displayed bound. For each two-root flag indicator , ordered degree regularity gives
Indeed, summing over outside gives , because codegree terms cancel; at most pairs meet . Regularity is required for all ordered , including equality, so both signs have this bound.
Certificate data. The first certificate has nine selectors and six positive semidefinite blocks: five with four roots and one with two. It uses the three-variable link rows with and without the non-edge factor, the two-variable indicator and rational-weight rows, and the two density products above. The second has 38 blocks: three with two roots and 35 with four. Its scalar rows comprise 80 local, eight cut, nine density and 12,750 three-variable link rows, and 120 signed regularity rows. Each matrix entry is the joint indicator of its two flags on the appropriate disjoint free sets; the matrix pairing includes both ordered off-diagonal terms. In every case coefficients are rebuilt by averaging all 720 orders of a class. With color 1 assigned to , bad edges have color sum zero or two and missing triples have color sum one. This explains the exact target normalization by . These specifications, together with the rational certificate entries, determine (4) and (5) without any numerical optimization premise.
References
- [1]P. Graham, Checking material for The Turán density of the tight five-cycle, published with the paper (linked below the title). The formalization guide there is the file checks/FORMALIZATION.md. Toolchain: leanprover/lean4:v4.32.2; Mathlib revision 905b95818eb32af7874a58b427f50c1711a5e96c.
- [2]D. Mubayi and V. Rödl, On the Turán Number of Triple Systems, Journal of Combinatorial Theory, Series A 100 (2002), no. 1, 136–152. Author’s copy, Construction 1, p. 13: https://homepages.math.uic.edu/~mubayi/papers/hypturan.pdf.DOI
- [3]D. Mubayi, O. Pikhurko and B. Sudakov, Hypergraph Turán Problem: Some Open Questions, October 10, 2011, §2.4, Conjecture 7, p. 3. https://rose-kiwi.lnx.warwick.ac.uk/E/MubayiPikhurkoSudakovv11aim.pdf.
- [4]N. Kamčev, S. Letzter and A. Pokrovskiy, The Turán Density of Tight Cycles in Three-Uniform Hypergraphs, International Mathematics Research Notices 2024 (2024), no. 6, 4804–4841. Numbering follows arXiv:2209.08134v3 (October 6, 2023; first posted September 16, 2022). https://arxiv.org/abs/2209.08134v3.
- [5]L. Bodnár, J. León, X. Liu and O. Pikhurko, The Turán density of short tight cycles, arXiv:2506.03223v1 (first posted June 3, 2025). All numbered references follow the versioned PDF. https://arxiv.org/abs/2506.03223v1.
- [6]L. Bodnár, J. León, X. Liu and O. Pikhurko, The Turán number of {C₅, K₄}, supplementary notebook, introduction and zero-based code cells 1–6, June 3, 2025. https://github.com/bodnallev/supplementary_files/blob/57663246d010d2a4a66271c0fb38460cd377985b/no_cl/no_c5_k4.ipynb.
- [7]V. Falgas-Ravry and E. R. Vaughan, Turán H-densities for 3-graphs, Electronic Journal of Combinatorics 19 (2012), no. 3, P40. Numbering follows arXiv:1201.4326v1 (first posted January 20, 2012). https://arxiv.org/abs/1201.4326v1.
- [8]H. Huang, On the maximum induced density of directed stars and related problems, arXiv:1303.3101v2 (March 17, 2013; first posted March 13, 2013). https://arxiv.org/abs/1303.3101v2.
- [10]L. Bodnár, FlagAlgebraToolbox: Flag Algebra Computations in SageMath, arXiv:2601.06590v3 (September 12, 2026; first posted January 10, 2026). This version documents release 0.3; the earlier supplementary notebook [6] does not identify a release tag. https://arxiv.org/abs/2601.06590v3.
- [11]G. Jeong, S. Park, S. Im, J. Lee and H. Yang, A New Upper Bound for the Turán Density of the Tetrahedron, arXiv:2609.27495v2 (October 2, 2026; first posted September 23, 2026). https://arxiv.org/abs/2609.27495v2.
- [12]X. Liu, C53_count.ipynb, edge-density objective and saved output, February 6, 2026, repository revision 1b5c8b15c545ea15587f8240bd2149a29aaba857. https://github.com/xliu2022/xliu2022.github.io/blob/1b5c8b15c545ea15587f8240bd2149a29aaba857/FlagAlgebra_Certificate/HypergraphGeneralizeTuran/script/C53_count.ipynb.
- [13]A. Ferudun, An Exact Logarithmic-Slate Algorithm for Recursive Tight-Cycle Constructions, version 1.0, October 16, 2026. https://doi.org/10.5281/zenodo.234214446.
- [14]Ulam.AI, UnsolvedMath, record AIM-COMBINATORICS-0153 (record id 20001028), research summary on recursive tight-cycle constructions. The record metadata is dated August 14, 2026. Only the pinned dataset record was read, not the underlying attempt or proof. https://huggingface.co/datasets/ulamai/UnsolvedMath/blob/d371ee917ac9647fbb06cd6fc529deec6f3dda82/dataset.json.
- [15]L. Bodnár, J. León, X. Liu and O. Pikhurko, The Turán density of the tight 5-cycle minus one edge, arXiv:2412.21011v3 (July 9, 2025; first posted December 30, 2024). https://arxiv.org/abs/2412.21011v3.
- [16]J. Balogh and H. Luo, Turán density of long tight cycle minus one hyperedge, arXiv:2303.10530v2 (March 3, 2024; first posted March 19, 2023). https://arxiv.org/abs/2303.10530v2.
- [17]B. Lidický, C. Mattes and F. Pfender, The Hypergraph Turán Densities of Tight Cycles Minus an Edge, arXiv:2409.14257v2 (November 26, 2024; first posted September 21, 2024). https://arxiv.org/abs/2409.14257v2.
- [18]B. Lidický and J. Volec, Solving Large SDPs from Flag Algebra Problems, arXiv:2610.33850v1 (October 24, 2026). https://arxiv.org/abs/2610.33850v1.
- [19]A. A. Razborov, Flag algebras, Journal of Symbolic Logic 72 (2007), no. 4, 1239–1282. https://doi.org/10.2178/jsl/1203350785.
- [20]A. A. Razborov, On 3-Hypergraphs with Forbidden 4-Vertex Configurations, SIAM J. Discrete Math. 24 (2010), no. 3, 946–963; the bound π(C₅³) < 0.4683 is on p. 962. https://doi.org/10.1137/090747476.
