### 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 language | English (US) |
---|---|

Pages (from-to) | 784-797 |

Number of pages | 14 |

Journal | Bulletin of the London Mathematical Society |

Volume | 49 |

Issue number | 5 |

DOIs | |

State | Published - 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

Ferber, A., Luh, K., & Nguyen, O. (2017). Embedding large graphs into a random graph:

*Bulletin of the London Mathematical Society*,*49*(5), 784-797. https://doi.org/10.1112/blms.12066