Fractional clique decompositions in random hypergraphs

Source 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.