Packing perfect matchings in random hypergraphs. Issue 3 (26th November 2017)

• Record Type: Journal Article
• Authors: Ferber, Asaf; Vu, Van
• Is Part Of: Random structures & algorithms. Volume 52:Issue 3(2018)
• Page Start: 367
• Page End: 378
• Publication Date: 2017-11-26
• Subjects: Perfect matching -- hypergraph -- random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20745
• Languages: English
• ISSNs: 1042-9832

Abstract

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.