The threshold for combs in random graphs1. Issue 4 (9th October 2015)

• Record Type: Journal Article
• Authors: Kahn, Jeff; Lubetzky, Eyal; Wormald, Nicholas
• Is Part Of: Random structures & algorithms. Volume 48:Issue 4(2016)
• Page Start: 794
• Page End: 802
• Publication Date: 2015-10-09
• Subjects: spanning trees in random graphs -- Comb Conjecture; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20614
• Languages: English
• ISSNs: 1042-9832

Abstract

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