Nonvertex-Balanced Factors in Random Graphs

We prove part of a conjecture by Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1-28.) regarding threshold functions for the existence of an H-factor in a random graph G(n,p). We prove that the conjectured threshold function is correct for any graph H which is not covered by its densest subgraphs. We also demonstrate that the main result of Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1-28) generalizes to multigraphs, digraphs, and a multipartite model.