Fractional clique decompositions in random hypergraphs
Abstract
We prove that, whenever $ p \ge n^{-1/2 + o(1)} $, with high probability $ G(n, p) $ admits a fractional triangle decomposition, that is, a non-negative weight function on its triangles for which the total weight of all triangles containing each edge is equal to 1. This bound on $ p $ is optimal up to the asymptotic error term, improving upon the recent state of the art, due to Mahabaduge and Simkin, that $ p \ge n^{-4/11 + o(1)} $ suffices. Our main tool is a deterministic theorem guaranteeing the existence of fractional clique decompositions in all hypergraphs satisfying suitable `clique-regularity' properties. We prove this by analysing an extension (and generalisation to hypergraphs) of an algorithm proposed by Mahabaduge and Simkin, in which, at each time step, the discrepancy at each edge is spread among its containing triangles. By showing the concentration of the relevant quantities in random $ k $-uniform hypergraphs, we obtain for all $ k \ge 2 $ and $ r \ge k + 1 $ that w.h.p. $ G^{(k)}(n, p) $ admits a fractional $ K^{(k)}_r $-decomposition whenever $ p \ge n^{-\frac{r - k}{\binom{r}{k} - 1} + o(1)} $, which improves upon results of Delcourt, Kelly, and Postle, and is best possible up to subpolynomial factors.
Related
- The threshold for fractional clique decompositions of random hypergraphs, via matrix scaling
- An improved minimum degree threshold for fractional clique decompositions in partite graphs
- Clique-factors in randomly perturbed hypergraphs
- On the distinct maximal-clique sizes in k-uniform hypergraphs
- Asymptotic Enumeration of F-decompositions in Typical Hypergraphs and of Universal Cycles
BibTeX
@misc{joos2026fractional,
title = {{Fractional clique decompositions in random hypergraphs}},
author = {Felix Joos and Zak Smith},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29943},
eprint = {2609.29943},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29943},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Fractional clique decompositions in random hypergraphs
AU - Felix Joos
AU - Zak Smith
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.29943
UR - https://arxiv.org/abs/2609.29943
AB - We prove that, whenever $ p \ge n^{-1/2 + o(1)} $, with high probability $ G(n, p) $ admits a fractional triangle decomposition, that is, a non-negative weight function on its triangles for which the total weight of all triangles containing each edge is equal to 1. This bound on $ p $ is optimal up to the asymptotic error term, improving upon the recent state of the art, due to Mahabaduge and Simkin, that $ p \ge n^{-4/11 + o(1)} $ suffices. Our main tool is a deterministic theorem guaranteeing the existence of fractional clique decompositions in all hypergraphs satisfying suitable `clique-regularity' properties. We prove this by analysing an extension (and generalisation to hypergraphs) of an algorithm proposed by Mahabaduge and Simkin, in which, at each time step, the discrepancy at each edge is spread among its containing triangles. By showing the concentration of the relevant quantities in random $ k $-uniform hypergraphs, we obtain for all $ k \ge 2 $ and $ r \ge k + 1 $ that w.h.p. $ G^{(k)}(n, p) $ admits a fractional $ K^{(k)}_r $-decomposition whenever $ p \ge n^{-\frac{r - k}{\binom{r}{k} - 1} + o(1)} $, which improves upon results of Delcourt, Kelly, and Postle, and is best possible up to subpolynomial factors.
ER -