Sharp threshold for embedding combs and other spanning trees in random graphs

Abstract

When $k|n$, the tree ${\mathrm{Comb}}_{n,k}$ consists of a path containing $n/k$ vertices, each of whose vertices has a disjoint path length $k-1$ beginning at it. We show that, for any $k=k(n)$ and $\epsilon >0$, the binomial random graph $\mathcal{G}(n,(1+\epsilon )\log n/n)$ almost surely contains ${\mathrm{Comb}}_{n,k}$ as a subgraph. This improves a recent result of Kahn, Lubetzky and Wormald. We prove a similar statement for a more general class of trees containing both these combs and all bounded degree spanning trees which have at least $\epsilon n/{\log }^{9}n$ disjoint bare paths length $\lceil {\log }^{9}n\rceil$. We also give an efficient method for finding large expander subgraphs in a binomial random graph. This allows us to improve a result on almost spanning trees by Balogh, Csaba, Pei and Samotij.

20 pages

References in corpus (1)

• Embedding bounded degree spanning trees in random graphs