Factors in random graphs

Let H be a fixed graph on v vertices. For an n‐vertex graph G with n divisible by v, an H‐factor of G is a collection of n/v copies of H whose vertex sets partition V (G). In this work, we consider the threshold thH(n) of the property that an Erdős‐Rényi random graph (on n points) contains an H‐factor. Our results determine thH(n) for all strictly balanced H. The method here extends with no difficulty to hypergraphs. As a corollary, we obtain the threshold for a perfect matching in random k‐uniform hypergraph, solving the well‐known “Shamir's problem.” © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008