Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 12 min ago
PreprintCC BY-NC-SA 4.0arXiv

An improved minimum degree threshold for fractional clique decompositions in partite graphs

  • Sean Longbrake
  • Michael Simkin
  • Liana Yepremyan
  • Michael Zheng
Open at sourcePDFDOICite

Abstract

We prove a Dirac-type condition for an r-partite graph to admit a fractional clique decomposition: every sufficiently large r-partite graph with n vertices in each part and partite minimum degree at least (1 − 1/30r2) n admits a fractional Kr-decomposition, subject to necessary divisibility conditions. This implies the same upper bound on the asymptotic minimum degree threshold for r-partite graphs to admit a Kr-decomposition, using a well-known reduction.

Related

  1. Fractional Triangle Decompositions at Partite Minimum Degree 4n/5
    Hengzhi He, Guang Cheng
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The threshold for fractional clique decompositions of random hypergraphs, via matrix scaling
    Tuan Tran
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  3. Graph Decompositions at the Expectation Threshold
    Jia-Qi Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  4. On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
    Chengli Li, Feng Liu
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref
  5. Fractional clique decompositions in random hypergraphs
    Felix Joos, Zak Smith
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{longbrake2026improved,
  title = {{An improved minimum degree threshold for fractional clique decompositions in partite graphs}},
  author = {Sean Longbrake and Michael Simkin and Liana Yepremyan and Michael Zheng},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.08432},
  eprint = {2611.08432},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.08432},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - An improved minimum degree threshold for fractional clique decompositions in partite graphs
AU  - Sean Longbrake
AU  - Michael Simkin
AU  - Liana Yepremyan
AU  - Michael Zheng
PY  - 2026
DA  - 2026/11/05
PB  - arXiv
DO  - 10.48550/arxiv.2611.08432
UR  - https://arxiv.org/abs/2611.08432
AB  - We prove a Dirac-type condition for an r-partite graph to admit a fractional clique decomposition: every sufficiently large r-partite graph with n vertices in each part and partite minimum degree at least (1 − 1/30r^2) n admits a fractional K_r-decomposition, subject to necessary divisibility conditions. This implies the same upper bound on the asymptotic minimum degree threshold for r-partite graphs to admit a K_r-decomposition, using a well-known reduction.
ER  -