View PDF HTML (experimental)

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ühn, 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$.

Submission history

From: Bertille Granet [view email]
[v1] Fri, 19 Jun 2026 15:44:55 UTC (26 KB)