The threshold for combs in random graphs |
| |
| Authors: | Jeff Kahn Eyal Lubetzky Nicholas Wormald |
| |
| Institution: | 1. Department of Mathematics, Rutgers, Piscataway, New Jersey;2. Courant Institute of Mathematical Sciences, New York University, New York, New York;3. School of Mathematical Sciences, Monash University, Clayton, Victoria, Australia |
| |
| Abstract: | For  let  denote the tree consisting of an  ‐vertex path with disjoint  ‐vertex paths beginning at each of its vertices. An old conjecture says that for any  the threshold for the random graph  to contain  is at  . Here we verify this for  with any fixed  . In a companion paper, using very different methods, we treat the complementary range, proving the conjecture for  (with  ). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 794–802, 2016 |
| |
| Keywords: | spanning trees in random graphs Comb Conjecture |
|
|
