Embedding large graphs into a random graph

作者：Ferber Asaf^*; Luh Kyle; Nguyen Oanh

来源：Bulletin of the London Mathematical Society, 2017, 49(5): 784-797.

DOI：10.1112/blms.12066

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

• 出版日期2017-10
• 单位MIT