Expertini Research Research
Mathematics PDF Available DOI: 10.1112/blms.12066 Non-peer-reviewed Preprint

Embedding large graphs into a random graph

Asaf Ferber, Kyle Luh, Oanh Nguyen  ·  Published 2016-06-19

Abstract

In this paper we consider the problem of embedding almost-spanning, bounded degree graphs in a random graph. In particular, let $\Delta\geq 5$, $\varepsilon > 0$ and let $H$ be a graph on $(1-\varepsilon)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.

Keywords

📄 Full Paper Available as PDF
This paper is available as a downloadable PDF.
📄 Download PDF

✨ AI Plain-English Summary

Get a plain-English summary of this paper generated by AI (5 free per day).

Comments (0)

No comments yet. Be the first to comment.