Determining decomposition thresholds for long odd cycles

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 $\hat{I}{´}_{C_{\ell }}$ is then the least real number such that any $n$-vertex graph $G$ with minimum degree at least $(\hat{I}{´}_{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 $\hat{I}{´}_{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 $\hat{I}{´}_{C_{\ell }}$ for larger odd values of $\ell$ (the behaviour of $\hat{I}{´}_{C_{\ell }}$ for even $\ell$ is different and well understood). A natural generalisation of Nash-Williams' conjecture implies that $\hat{I}{´}_{C_{\ell }}=\frac{\ell }{2\ell -2}$ for all odd $\ell \ge 3$. Here we prove that this conjecture holds for all $\ell \ge 73$.

21 pages