The threshold for combs in random graphs

Abstract

For $k\mid n$ let $Com{b}_{n,k}$ denote the tree consisting of an $(n/k)$-vertex path with disjoint $k$-vertex paths beginning at each of its vertices. An old conjecture says that for any $k=k(n)$ the threshold for the random graph $G(n,p)$ to contain $Com{b}_{n,k}$ is at $p\asymp \frac{\log n}{n}$. Here we verify this for $k\le C\log n$ with any fixed $C>0$. In a companion paper, using very different methods, we treat the complementary range, proving the conjecture for $k\ge {\kappa }_0\log n$ (with ${\kappa }_0\approx 4.82$).

9 pages

Cited by in corpus (1)

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