Non-Vertex-Balanced Factors in Random Graphs

Stefanie Gerke, Andrew McDowell

Published 2013-04-10Version 1

We prove part of a conjecture by Johansson, Kahn and Vu \cite{JKV} regarding threshold functions for the existence of an $H$-factor in a random graph \gnp. 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 \cite{JKV} generalises to multigraphs, digraphs, and a multipartite model.