Perfect matchings in random uniform hypergraphs

Let ℋ k ( n , p ) be the random k ‐uniform hypergraph on V = [ n ] with edge probability p . Motivated by a theorem of Erdős and Rényi 7 regarding when a random graph G ( n , p ) = ℋ 2 ( n , p ) has a perfect matching, the following conjecture may be raised. (See J. Schmidt and E. Shamir 16 for a weaker version.) Conjecture. Let k | n for fixed k ≥ 3, and the expected degree d ( n , p ) = p (   k −1 n −1 ). Then$$\hbox{Pr}[{\cal H}_k(n, p)\hbox{ has a perfect matching}] \rightarrow \left\{\matrix{0\hfill & \hbox{if }d(n, p) - \ln n \rightarrow -\infty\hfill\cr e^{-e^{-c}}\hfill & \hbox{if }d(n, p) - \ln n \rightarrow c,\hfill\cr 1\hfill & \hbox{if }d(n, p) - \ln n \rightarrow \,\infty.\hfill\cr}\right. $$(Erdős and Rényi 7 proved this for G ( n , p ).) Assuming d ( n , p )/ n 1/2 → ∞, Schmidt and Shamir 16 were able to prove that ℋ k ( n , p ) contains a perfect matching with probability 1 − o (1). Frieze and Janson 8 showed that a weaker condition d ( n , p )/ n 1/3 → ∞ was enough. In this paper, we further weaken the condition to$${{d(n, p)} \over {n^{1/(5+2/(k-1))}}} \rightarrow \infty.$$ A condition for a similar problem about a perfect triangle packing of G ( n , p ) is also obtained. A perfect triangle packing of a graph is a collection of vertex disjoint triangles whose union is the entire vertex set. Improving a condition p ≥ cn −2/3+1/15 of Krivelevich 12, it is shown that if 3| n and p ≫ n −2/3+1/18 , then$$\hbox{Pr}[G(n, p)\hbox{ has a perfect triangle packing}] = 1 - o(1).$$ © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 111–132, 2003