Skip to content
DraconiticResearch
Search Sources API
181,713 studies31 sourcesUpdated 55 min ago
PreprintarXiv licencearXiv

The threshold for fractional clique decompositions of random hypergraphs, via matrix scaling

  • Tuan Tran
Open at sourcePDFDOICite

Abstract

Let δ*k,r be the fractional Kr(k)-decomposition threshold in minimum codegree. For fixed k≥2, r≥ k+1 and ε>0, we prove that every n-vertex k-uniform hypergraph G with minimum codegree at least (δ*k,r+ε)n admits, with high probability, a fractional Kr(k)-decomposition after retaining each edge independently with probability p ≥ C(log n/nr−k)1/(binomrk−1). The bound on p is sharp up to a constant factor, confirming the conjectured threshold order in the graph case. The proof develops a probabilistic matrix-scaling approach.

Related

  1. Fractional clique decompositions in random hypergraphs
    Felix Joos, Zak Smith
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Clique-factors in randomly perturbed hypergraphs
    Yulin Chang, Jie Han, Patrick Morris +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. On the distinct maximal-clique sizes in k-uniform hypergraphs
    Jiabao Yang, Lixiang Yu, Leilei Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Asymptotic Enumeration of F-decompositions in Typical Hypergraphs and of Universal Cycles
    Danni Li, Bin Wang, Junxue Zhang
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Fractional Triangle Decompositions at Partite Minimum Degree 4n/5
    Hengzhi He, Guang Cheng
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{tran2026threshold,
  title = {{The threshold for fractional clique decompositions of random hypergraphs, via matrix scaling}},
  author = {Tuan Tran},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.00924},
  eprint = {2610.00924},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.00924},
}
RIS
TY  - UNPB
TI  - The threshold for fractional clique decompositions of random hypergraphs, via matrix scaling
AU  - Tuan Tran
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.00924
UR  - https://arxiv.org/abs/2610.00924
AB  - Let δ^*_k,r be the fractional K_r^(k)-decomposition threshold in minimum codegree. For fixed k≥2, r≥ k+1 and ε>0, we prove that every n-vertex k-uniform hypergraph G with minimum codegree at least (δ^*_k,r+ε)n admits, with high probability, a fractional K_r^(k)-decomposition after retaining each edge independently with probability p ≥ C(log n/n^r−k)^1/(binomrk−1). The bound on p is sharp up to a constant factor, confirming the conjectured threshold order in the graph case. The proof develops a probabilistic matrix-scaling approach.
ER  -