Embedding large graphs into a random graph:

Asaf Ferber, Kyle Luh, Oanh Nguyen

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

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
Volume49
Issue number5
DOIs
StatePublished - Oct 2017

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

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

  • Cite this