Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 24 min ago
PreprintCC BY 4.0arXiv

On decomposition thresholds for odd cycles

  • Jianfeng Hou
  • Caiyun Hu
  • Hezhi Wang
Open at sourcePDFDOICite

Abstract

We determine the asymptotic minimum-degree threshold for decompositions into cycles of a fixed odd length. We prove that, for each odd integer ℓ≥3, every eps>0 and sufficiently large n, every n-vertex Cℓ-divisible graph G with minimum degree δ(G)≥ (ℓ/(2ℓ−2)+eps)n has a Cℓ-decomposition, where Cℓ denotes the cycle of length ℓ. This settles the remaining cases ℓ=5,7,…,71 and completes the determination of the thresholds for all odd cycles. Our main ingredient is a sharp fractional decomposition theorem for weighted triangles: for every real a≥ 1,every n-vertex graph G with δ(G)≥ (1/2+1/(2(a+1)))n admits a fractional decomposition into triangles with edge weights a,1,1.

Related

  1. Large tight components and Dirac thresholds for tight Hamilton cycles
    Hao Lin, Guanghui Wang, Jiande Zhang +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Even cycle decomposition thresholds for dense multipartite graphs
    Weiyi Sun, Tao Feng, Shikang Yu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Improved thresholds for e-values
    Christopher Blier-Wong, Ruodu Wang
    The Annals of StatisticsPeer-reviewedLicence not statedFull text10 citedStatisticsOpenAlex
  4. ACC for lc thresholds for algebraically integrable foliations
    Omprokash Das, Jihao Liu, Roktim Mascharak
    Selecta MathematicaPeer-reviewedLicence not statedFull text10 citedGeometry & topologyOpenAlex
  5. A dimension-free comparison between expectation thresholds and fractional expectation thresholds
    Jinyoung Park
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{hou2026decomposition,
  title = {{On decomposition thresholds for odd cycles}},
  author = {Jianfeng Hou and Caiyun Hu and Hezhi Wang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.23471},
  eprint = {2610.23471},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.23471},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On decomposition thresholds for odd cycles
AU  - Jianfeng Hou
AU  - Caiyun Hu
AU  - Hezhi Wang
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2610.23471
UR  - https://arxiv.org/abs/2610.23471
AB  - We determine the asymptotic minimum-degree threshold for decompositions into cycles of a fixed odd length. We prove that, for each odd integer ℓ≥3, every eps>0 and sufficiently large n, every n-vertex C_ℓ-divisible graph G with minimum degree δ(G)≥ (ℓ/(2ℓ−2)+eps)n has a C_ℓ-decomposition, where C_ℓ denotes the cycle of length ℓ. This settles the remaining cases ℓ=5,7,…,71 and completes the determination of the thresholds for all odd cycles. Our main ingredient is a sharp fractional decomposition theorem for weighted triangles: for every real a≥ 1,every n-vertex graph G with δ(G)≥ (1/2+1/(2(a+1)))n admits a fractional decomposition into triangles with edge weights a,1,1.
ER  -