The threshold for combs in random graphs

Jeff Kahn; Eyal Lubetzky; Nicholas Wormald

doi:10.1002/rsa.20614

The threshold for combs in random graphs

Jeff Kahn, Eyal Lubetzky, Nicholas Wormald

Mathematics

Research output: Contribution to journal › Article › peer-review

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	https://doi.org/10.1002/rsa.20614
State	Published - Jul 1 2016

Keywords

Comb Conjecture
Spanning trees in random graphs

ASJC Scopus subject areas

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

Access to Document

10.1002/rsa.20614

Cite this

@article{d49f53fc22f34d25ba089025abf698ab,

title = "The threshold for combs in random graphs",

abstract = "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).",

keywords = "Comb Conjecture, Spanning trees in random graphs",

author = "Jeff Kahn and Eyal Lubetzky and Nicholas Wormald",

note = "Publisher Copyright: {\textcopyright} 2015 Wiley Periodicals, Inc.",

year = "2016",

month = jul,

day = "1",

doi = "10.1002/rsa.20614",

language = "English (US)",

volume = "48",

pages = "794--802",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "4",

}

TY - JOUR

T1 - The threshold for combs in random graphs

AU - Kahn, Jeff

AU - Lubetzky, Eyal

AU - Wormald, Nicholas

PY - 2016/7/1

Y1 - 2016/7/1

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

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

KW - Comb Conjecture

KW - Spanning trees in random graphs

UR - http://www.scopus.com/inward/record.url?scp=84944112069&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84944112069&partnerID=8YFLogxK

U2 - 10.1002/rsa.20614

DO - 10.1002/rsa.20614

M3 - Article

AN - SCOPUS:84944112069

SN - 1042-9832

VL - 48

SP - 794

EP - 802

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 4

ER -

The threshold for combs in random graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this