Premium
Packing perfect matchings in random hypergraphs
Author(s) -
Ferber Asaf,
Vu Van
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20745
Subject(s) - hypergraph , mathematics , combinatorics , disjoint sets , integer (computer science) , binomial (polynomial) , random graph , discrete mathematics , graph , integer programming , algorithm , computer science , statistics , programming language
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 hypergraphH n , p kcontains N : = ( 1 − o ( 1 ) ) (n − 1k − 1) p edge‐disjoint perfect matchings, provided p ≥log C nn 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.