Factors in random graphs

Abstract

Let $H$ be a fixed graph on $v$ vertices. For an $n$-vertex graph $G$ with $n$ divisible by $v$, an $H$-{\em factor} of $G$ is a collection of $n/v$ copies of $H$ whose vertex sets partition $V(G)$. In this paper we consider the threshold $t{h}_H(n)$ of the property that an Erdős-Rényi random graph (on $n$ points) contains an $H$-factor. Our results determine $t{h}_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."

To appear in Random Structures and Algorithms