### 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(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 language | English (US) |
---|---|

Pages (from-to) | 794-802 |

Number of pages | 9 |

Journal | Random Structures and Algorithms |

Volume | 48 |

Issue number | 4 |

DOIs | |

State | Published - Jul 1 2016 |

### Keywords

- Comb Conjecture
- Spanning trees in random graphs

### ASJC Scopus subject areas

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics

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

## Cite this

Kahn, J., Lubetzky, E., & Wormald, N. (2016). The threshold for combs in random graphs.

*Random Structures and Algorithms*,*48*(4), 794-802. https://doi.org/10.1002/rsa.20614