Skip to content
DraconiticResearch
Search Sources API
186,123 studies31 sourcesUpdated 30 min ago
PreprintarXiv licencearXiv

Fractional Triangle Decompositions at Partite Minimum Degree 4n/5

  • Hengzhi He
  • Guang Cheng
Open at sourcePDFDOICite

Abstract

We prove that every triangle-divisible balanced tripartite graph whose vertex classes have size n and whose partite minimum degree is at least 4n/5 admits a fractional triangle decomposition. Combined with the multipartite decomposition theorem of Barber, Kühn, Lo, Osthus, and Taylor, this implies that, for every fixed ε<1/5 and all sufficiently large n, every ε-dense partial Latin square of order n is completable, improving the previous asymptotic bound of 2/25. The fractional decomposition theorem is finite and exact. Its proof uses a minimum-weight perfect matching to normalize an arbitrary Farkas dual weighting, followed by an explicit direct-and-two-step routing scheme whose aggregate congestion on every off-matching edge is at most one.

Related

  1. Minkowski Decompositions for Generic Infinitesimal Newton-Okounkov Bodies of Arbitrary-Degree External Tensor Products on Products of Curves
    Yi Lu
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  2. Minimum Distance Spectral Radius of Tree with Given Maximum Degree
    Yifei Li, Zia Ullah Khan
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. The threshold for fractional clique decompositions of random hypergraphs, via matrix scaling
    Tuan Tran
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  4. Positive Square Energy of Graphs with Minimum Degree at Least Two
    S. Akbari, Fu-Tao Hu, Ya-Yang Liu
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  5. On the minimum number of triangles in balanced tripartite graphs with large minimum degree
    Chunqiu Fang, Rongxing Xu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{he2026fractional,
  title = {{Fractional Triangle Decompositions at Partite Minimum Degree $4n/5$}},
  author = {Hengzhi He and Guang Cheng},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.31758},
  eprint = {2609.31758},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.31758},
}
RIS
TY  - UNPB
TI  - Fractional Triangle Decompositions at Partite Minimum Degree 4n/5
AU  - Hengzhi He
AU  - Guang Cheng
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.31758
UR  - https://arxiv.org/abs/2609.31758
AB  - We prove that every triangle-divisible balanced tripartite graph whose vertex classes have size n and whose partite minimum degree is at least 4n/5 admits a fractional triangle decomposition. Combined with the multipartite decomposition theorem of Barber, Kühn, Lo, Osthus, and Taylor, this implies that, for every fixed ε<1/5 and all sufficiently large n, every ε-dense partial Latin square of order n is completable, improving the previous asymptotic bound of 2/25. The fractional decomposition theorem is finite and exact. Its proof uses a minimum-weight perfect matching to normalize an arbitrary Farkas dual weighting, followed by an explicit direct-and-two-step routing scheme whose aggregate congestion on every off-matching edge is at most one.
ER  -