Packing perfect matchings in random hypergraphs. Issue 3 (26th November 2017) - Ferber, Asaf; Vu, Van
Abstract: We introduce a new procedure for generating the binomial random graph/hypergraph models, referred to as online sprinkling . As an illustrative application of this method, we show that for any fixed integer k ≥ 3, the binomial k ‐uniform random hypergraph H n, p k contains N : = ( 1 − o ( 1 ) ) ( n − 1 k − 1 ) p edge‐disjoint perfect matchings, provided p ≥ log ⁡ C n n k − 1, where C : = C ( k ) is an integer depending only on k . Our result for N is asymptotically optimal and for p is optimal up to the p o l y l o g ( n ) factor. This significantly improves a result of Frieze and Krivelevich.