Embedding large graphs into a random graph

Abstract

In this paper we consider the problem of embedding almost-spanning, bounded degree graphs in a random graph. In particular, let $\Delta \ge 5$, $\epsilon >0$ and let $H$ be a graph on $(1-\epsilon )n$ vertices and with maximum degree $\Delta$. We show that a random graph $G_{n,p}$ with high probability contains a copy of $H$, provided that $p\gg (n^{-1}{\log }^{1/\Delta }n{)}^{2/(\Delta +1)}$. Our assumption on $p$ is optimal up to the $polylog$ factor. We note that this $polylog$ term matches the conjectured threshold for the spanning case.

Incorporated referee comments. To appear in Bulletin of the London Mathematical Society