For k|n let Combn,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 Combn,k is at p(equivalent to)logn/n. Here we verify this for k≤Clogn with any fixed C>0. In a companion paper, using very different methods, we treat the complementary range, proving the conjecture for k≥κ0logn (with κ0≈4.82).
- Comb Conjecture
- Spanning trees in random graphs
ASJC Scopus subject areas
- Computer Graphics and Computer-Aided Design
- Applied Mathematics