Embedding spanning trees in random graphs

Опубликовано 17 августа 2016, 22:03

We prove that if T is a tree on n vertices with maximum degree D and the edge probability p(n) satisfies: np c max{D*log n,n^{\epsilon}} for some positive \epsilon0, then with high probability (w.h.p.) the random graph G(n,p) contains a copy of T. In particular, G(n,n^{-1+\epsilon}) w.h.p. contains a copy of any given bounded degree tree T on n vertices. The obtained bound on the edge probability is shown to be essentially tight for D=n^{\Theta(1)}.