PERFECT MATCHINGS IN RANDOM S-UNIFORM HYPERGRAPHS

Let E={X(1),X(2),...,X(m)} where the X(i) subset of or equal to V for 1 less than or equal to i less than or equal to m are distinct. The hy pergraph G=(V,E) is said to be s-uniform if \X(1)\=s for 1 less than o r equal to i less than or equal to m. A set of edges M={X(i) : i is an element of I} is a perfect matching if (i) i not equal j is an elemen t of I implies X(i) boolean AND X(i) = 0, and (ii) U-i is an element o f I X(i)=V. In this article we consider the question of whether a rand om s-uniform hypergraph contains a perfect matching. Let s greater tha n or equal to 3 be fixed and m/n(4/3)-->infinity. We show that an s-un iform hypergraph with m edges chosen uniformly from [74] contains a pe rfect matching with high probability. This improves an earlier result of Schmidt and Shamir who showed that m/n(3/2)-->infinity suffices. (C ) 1995 John Wiley and Sons, Inc.