The threshold for combs in random graphs

Jeff Kahn, Eyal Lubetzky, Nicholas Wormald

Research output: Contribution to journalArticlepeer-review


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).

Original languageEnglish (US)
Pages (from-to)794-802
Number of pages9
JournalRandom Structures and Algorithms
Issue number4
StatePublished - Jul 1 2016


  • Comb Conjecture
  • Spanning trees in random graphs

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'The threshold for combs in random graphs'. Together they form a unique fingerprint.

Cite this