Embedding large graphs into a random graph:

Asaf Ferber, Kyle Luh, Oanh Nguyen

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)784-797
Number of pages14
JournalBulletin of the London Mathematical Society
Issue number5
StatePublished - Oct 2017

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'Embedding large graphs into a random graph:'. Together they form a unique fingerprint.

Cite this