pith. sign in

arxiv: 2606.21548 · v1 · pith:4QTUESE2new · submitted 2026-06-19 · 🧮 math.CO

Determining decomposition thresholds for long odd cycles

Bertille Granet , Daniel Horsley This is my paper

Pith reviewed 2026-06-26 13:37 UTC · model grok-4.3

classification 🧮 math.CO
keywords cycle decompositiondecomposition thresholdodd cyclesNash-Williams conjectureminimum degreegraph partitioning
0
0 comments X

The pith

Any n-vertex graph with minimum degree at least (ℓ/(2ℓ-2) + o(1))n has an ℓ-cycle decomposition for odd ℓ at least 73 when ℓ divides the edge count and all degrees are even.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the asymptotic minimum degree threshold δ_{C_ℓ} for an ℓ-cycle decomposition equals ℓ/(2ℓ-2) when ℓ is odd and at least 73. This confirms the natural generalization of Nash-Williams' conjecture on triangle decompositions, which Delcourt and Postle recently settled for ℓ=3. The result shows that for these longer odd cycles the threshold matches the conjectured value exactly. A reader would care because the theorem pins down the precise density at which the edge set of a dense graph can be partitioned into cycles of a fixed odd length.

Core claim

The ℓ-cycle decomposition threshold δ_{C_ℓ} equals ℓ/(2ℓ-2) for every odd integer ℓ at least 73. Equivalently, every n-vertex graph whose minimum degree is at least (ℓ/(2ℓ-2) + o(1))n admits an ℓ-cycle decomposition precisely when ℓ divides the number of edges and every vertex has even degree.

What carries the argument

The cycle decomposition threshold δ_{C_ℓ}, the infimum of real numbers such that minimum degree above that value times n forces an ℓ-cycle decomposition under the natural divisibility conditions.

If this is right

  • The conjectured formula δ_{C_ℓ} = ℓ/(2ℓ-2) holds for every odd ℓ at least 73.
  • Above the threshold the only obstructions to an ℓ-cycle decomposition are the obvious divisibility conditions on edges and degrees.
  • The threshold takes the same functional form for all sufficiently long odd cycles as it does for triangles.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The finitely many remaining odd lengths below 73 may still satisfy the same threshold, though the current argument requires ℓ large enough.
  • The result reduces the general conjecture to checking a finite list of small odd cycle lengths.
  • The same degree condition may govern decompositions into cycles of mixed lengths when all lengths are odd and sufficiently large.

Load-bearing premise

The recent resolution of the triangle decomposition conjecture can be used as a black box to control the decomposition for longer odd cycles.

What would settle it

A concrete n-vertex graph with minimum degree (ℓ/(2ℓ-2) - ε)n for small ε>0, all degrees even, |E(G)| divisible by ℓ, yet containing no collection of ℓ-cycles that partition the edge set, for some fixed odd ℓ at least 73.

read the original abstract

An $\ell$-cycle decomposition of a graph $G$ is a set of $\ell$-cycles in $G$ whose edge sets partition the edge set of $G$. The $\ell$-cycle decomposition threshold $\delta_{C_\ell}$ is then the least real number such that any $n$-vertex graph $G$ with minimum degree at least $(\delta_{C_\ell}+o(1))n$ has an $\ell$-cycle decomposition if and only if $\ell$ divides $|E(G)|$ and each vertex of $G$ has even degree. Nash-Williams' famous conjecture on triangle decompositions states, asymptotically, that $\delta_{C_3}=\frac{3}{4}$. A very recent breakthrough result of Delcourt and Postle completely resolved this conjecture, however, Glock, K\"uhn, and Osthus have posed the problem of determining $\delta_{C_\ell}$ for larger odd values of $\ell$ (the behaviour of $\delta_{C_\ell}$ for even $\ell$ is different and well understood). A natural generalisation of Nash-Williams' conjecture implies that $\delta_{C_\ell}=\frac{\ell}{2\ell-2}$ for all odd $\ell \geq 3$. Here we prove that this conjecture holds for all $\ell \geq 73$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript proves that the ℓ-cycle decomposition threshold δ_{C_ℓ} equals ℓ/(2ℓ-2) for all odd integers ℓ ≥ 73. Under the necessary conditions that ℓ divides |E(G)| and every vertex has even degree, any n-vertex graph with minimum degree at least (ℓ/(2ℓ-2) + o(1))n admits an ℓ-cycle decomposition. The argument extends the Delcourt-Postle resolution of the ℓ=3 (Nash-Williams) case to longer odd cycles.

Significance. If the proof is correct, the result is significant: it confirms the natural generalization of Nash-Williams' conjecture for every odd ℓ at least 73, thereby determining the exact asymptotic threshold for all sufficiently long odd cycles. The work shows that the recent triangle breakthrough adapts to larger ℓ without introducing free parameters or ad-hoc adjustments, which strengthens the overall picture of cycle decomposition thresholds.

minor comments (3)
  1. [Abstract] Abstract: the statement that the result holds 'for all ℓ ≥ 73' would be clearer if it explicitly noted that the proof requires ℓ odd (already implicit from context but worth stating once).
  2. The dependence on the Delcourt-Postle theorem is central; a short dedicated subsection summarizing the precise properties imported from that work (e.g., which lemmas are black-boxed) would improve readability.
  3. [Introduction] Notation for the o(1) term in the minimum-degree condition should be defined once in the introduction with an explicit reference to the n→∞ limit.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending minor revision. We are pleased that the extension of the Delcourt-Postle result to odd cycles of length at least 73 is viewed as significant.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes the conjecture δ_{C_ℓ} = ℓ/(2ℓ-2) for odd ℓ ≥ 73 by extending the independent Delcourt-Postle resolution of the ℓ=3 case. The load-bearing step is an external prior result by different authors, with no self-definitional reductions, fitted inputs renamed as predictions, or self-citation chains that carry the central claim. The derivation is self-contained against the stated external benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No new free parameters or invented entities are introduced; the work proves an existing conjecture using known techniques for large parameters.

axioms (1)
  • standard math Standard graph theory axioms including the definition of cycle decompositions and minimum degree conditions
    The paper uses established definitions and prior theorems in the field.

pith-pipeline@v0.9.1-grok · 5761 in / 1187 out tokens · 43817 ms · 2026-06-26T13:37:41.436134+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 15 canonical work pages

  1. [1]

    B. R. Alspach. The wonderful Walecki construction.Bulletin of the Institute of Combinatorics and its Applications, 52:7–20, 2008

    2008

  2. [2]

    Barber, D

    B. Barber, D. K¨ uhn, A. Lo, and D. Osthus. Edge-decompositions of graphs with high minimum degree.Advances in Mathematics, 288:337–385, 2016. doi: 10.1016/j.aim.2015.09.032

    work page doi:10.1016/j.aim.2015.09.032 2016

  3. [3]

    Bryant, P

    D. Bryant, P. Dukes, D. Horsley, B. Maenhaut, and R. Montgomery. On decomposition thresholds for odd-length cycles and other tripartite graphs.arXiv preprint, 2024. arxiv:2411.17232

    Pith/arXiv arXiv 2024

  4. [4]

    Csaba, D

    B. Csaba, D. K¨ uhn, A. Lo, D. Osthus, and A. Treglown. Proof of the 1-factorization and Hamilton decomposition conjectures.Memoirs of the American Mathematical Society, 244(1154), 2016. doi: 10.1090/memo/1154

    work page doi:10.1090/memo/1154 2016

  5. [5]

    Delcourt, C

    M. Delcourt, C. Henderson, T. Lesgourgues, and L. Postle. Beyond Nash-Williams: Counterexamples to clique decomposition thresholds for all cliques larger than triangles.arXiv preprint, 2025. arXiv.2508.20819

    arXiv 2025

  6. [6]

    Delcourt and L

    M. Delcourt and L. Postle. Progress towards Nash-Williams’ conjecture on triangle decompositions.Journal of Combinatorial Theory, Series B, 146:382–416, 2021. doi: 10.1016/j.jctb.2020.09.008

    work page doi:10.1016/j.jctb.2020.09.008 2021

  7. [7]

    Delcourt and L

    M. Delcourt and L. Postle. A proof of Nash-Williams’ conjecture.arXiv preprint, 2026. arXiv:2606.11178

    Pith/arXiv arXiv 2026

  8. [8]

    F. Dross. Fractional triangle decompositions in graphs with large minimum degree.SIAM Journal on Discrete Mathematics, 30(1):36–42, 2016. doi: 10.1137/15M1014310

    work page doi:10.1137/15m1014310 2016

  9. [9]

    P. J. Dukes and D. Horsley. On the minimum degree required for a triangle decomposition.SIAM Journal on Discrete Mathematics, 34(1):597–610, 2020. doi: 10.1137/19M1284610

    work page doi:10.1137/19m1284610 2020

  10. [10]

    L. R. Ford Jr and D. R. Fulkerson. Maximal flow through a network.Canadian Journal of Mathematics, 8:399–404,

  11. [11]

    doi: 10.4153/CJM-1956-045-5

    work page doi:10.4153/cjm-1956-045-5 1956

  12. [12]

    Garaschuk.Linear methods for rational triangle decompositions

    K. Garaschuk.Linear methods for rational triangle decompositions. PhD thesis, University of Victoria, 2014

    2014

  13. [13]

    Glock, D

    S. Glock, D. K¨ uhn, A. Lo, R. Montgomery, and D. Osthus. On the decomposition threshold of a given graph. Journal of Combinatorial Theory, Series B, 139:47–127, 2019. doi: 10.1016/j.jctb.2019.02.010

    work page doi:10.1016/j.jctb.2019.02.010 2019

  14. [14]

    Glock, D

    S. Glock, D. K¨ uhn, and D. Osthus. Extremal aspects of graph and hypergraph decomposition problems. InSur- veys in Combinatorics 2021, London Mathematical Society Lecture Note Series 470, pages 235–265. Cambridge University Press, 2021. doi: 10.1017/9781009036214.007

    work page doi:10.1017/9781009036214.007 2021

  15. [15]

    P. E. Haxell and V. R¨ odl. Integer and fractional packings in dense graphs.Combinatorica, 21(1):13–38, 2001. doi: 10.1007/s004930170003

    work page doi:10.1007/s004930170003 2001

  16. [16]

    Joos and M

    F. Joos and M. K¨ uhn. Fractional cycle decompositions in hypergraphs.Random Structures & Algorithms, 61(3):425–443, 2022. doi: 10.1002/rsa.21070

    work page doi:10.1002/rsa.21070 2022

  17. [17]

    T. P. Kirkman. On a problem in combinations.Cambridge and Dublin Mathematical Journal, 2:191–204, 1847

  18. [18]

    Lucas.R´ ecr´ eations Math´ ematiques, volume II

    ´E. Lucas.R´ ecr´ eations Math´ ematiques, volume II. Gauthier-Villars, 1883

  19. [19]

    W. Mantel. Solution to problem 28, by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh, and W.A. Wythoff.Wiskundige Opgaven, 10:60–61, 1907

    1907

  20. [20]

    Montgomery

    R. Montgomery. Fractional clique decompositions of dense graphs.Random Structures & Algorithms, 54(4):779– 796, 2019. doi: 10.1002/rsa.20809

    work page doi:10.1002/rsa.20809 2019

  21. [21]

    A. Taylor. On the exact decomposition threshold for even cycles.Journal of Graph Theory, 90(3):231–266, 2019. doi: 10.1002/jgt.22399

    work page doi:10.1002/jgt.22399 2019

  22. [22]

    R. M. Wilson. An existence theory for pairwise balanced designs, III: Proof of the existence conjectures.Journal of Combinatorial Theory, Series A, 18(1):71–79, 1975. doi: 10.1016/0097-3165(75)90067-9

    work page doi:10.1016/0097-3165(75)90067-9 1975

  23. [23]

    R. Yuster. Packing and decomposition of graphs with trees.Journal of Combinatorial Theory, Series B, 78(1):123– 140, 2000. doi: 10.1006/jctb.1999.1934

    work page doi:10.1006/jctb.1999.1934 2000

  24. [24]

    R. Yuster. The decomposition threshold for bipartite graphs with minimum degree one.Random Structures & Algorithms, 21(2):121–134, 2002. doi: 10.1002/rsa.10044

    work page doi:10.1002/rsa.10044 2002

  25. [25]

    Zhang and G

    M. Zhang and G. Ge. Progress towards generalized Nash-Williams’ conjecture onK 4-decompositions.arXiv preprint, 2025. arXiv.2510.07783

    arXiv 2025