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 th(H) (n) of the property that an Erdos-Renyi random graph (on n points) contains an H-factor. Our results determine th(H) (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." (C) 2008 Wiley Periodicals, Inc.