The threshold for combs in random graphs

2014/01/13 by Jeff Kahn, Kahn, Jeff, Eyal Lubetzky +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1401.2710

openalex publication_date 2014/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For k| n let Comb_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 Comb_n,k is at p\asymp \fraclog nn. Here we verify this for k ≤ Clog n with any fixed C>0. In a companion paper, using very different methods, we treat the complementary range, proving the conjecture for k≥ κ₀ log n (with κ₀≈ 4.82).

Cited by

• Spanning trees of bounded degree in random geometric graphs

Related

• Sharp threshold for embedding combs and other spanning trees in random graphs
• The range of a random walk on a comb
• Threshold numbers of some graphs
• On the threshold for k-regular subgraphs of random graphs
• Thresholds and expectation thresholds