The threshold for combs in random graphs1. Issue 4 (9th October 2015) - Kahn, Jeff; Lubetzky, Eyal; Wormald, Nicholas
Abstract: For k | n let C o m 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 C o m b n, k is at p ≍ log n n . Here we verify this for k ≤ 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 ≥ κ 0 log n (with κ 0 ≈ 4.82 ). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 794–802, 2016