Perfect matchings in random s‐uniform hypergraphs

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.