Packing perfect matchings in random hypergraphs

Abstract

We introduce a new procedure for generating the binomial random graph/hypergraph models, referred to as \emph{online sprinkling}. As an illustrative application of this method, we show that for any fixed integer $k\ge 3$, the binomial $k$-uniform random hypergraph $H_{n,p}^k$ contains $N:=(1-o(1))\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)p$ edge-disjoint perfect matchings, provided $p\ge \frac{{\log }^{C}n}{n^{k-1}}$, where $C:=C(k)$ is an integer depending only on $k$. Our result for $N$ is asymptotically best optimal and for $p$ is optimal up to the $polylog(n)$ factor.

Relevant citations have been added