Premium
Perfect matchings in random s‐uniform hypergraphs
Author(s) -
Frieze Alan,
Janson Svante
Publication year - 1995
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.3240070104
Subject(s) - hypergraph , combinatorics , mathematics , matching (statistics) , discrete mathematics , set (abstract data type) , computer science , statistics , programming language
Let E = {X 1 , X 2 …, X m } where the X i ⊆ V for 1 ≤ i ≤ m are distinct. The hypergraph G = ( V, E ) is said to be s‐uniform if | X 1 | = s for 1 ≤ i ≤ m. A set of edges M = { X i : i ϵ I } is a perfect matching if (i) i ≠ j ϵ I implies X i ∩ X i = 0, and (ii) ∪ i ϵ I X i = V . In this article we consider the question of whether a random s ‐uniform hypergraph contains a perfect matching. Let s ≥ 3 be fixed and m/n 4/3 → ∞. We show that an s ‐uniform hypergraph with m edges chosen uniformly from [74] contains a perfect matching with high probability. This improves an earlier result of Schmidt and Shamir who showed that m/n 3/2 → ∞ suffices. © 1995 John Wiley & Sons, Inc.