Embedding large graphs into a random graph:

In this paper we consider the problem of embedding almost-spanning, bounded degree graphs in a random graph. In particular, let Δ≥5, ϵ>0, and let H be a graph on (1-ϵ)n vertices and with maximum degree Δ. We show that a random graph Gn,p with high probability contains a copy of H, provided that p≫(n-1log1/Δn)2/(Δ+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.