Perfect matchings in random s-uniform hypergraphs

Let E = {X₁, X₂…, 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₁| = 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.