The threshold for combs in random graphs

DOI10.1002/RSA.20614MaRDI QIDQ5740276zbMATH OpenOpenAlexFDO

Authors Eyal Lubetzky, J. Kahn, Nicholas Wormald

Publication date 25 July 2016

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.2710

zbMATH Keywords

comb conjecturespanning trees in random graphs

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

Abstract: For $kmidn$ let $Com{b}_{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 $Com{b}_{n,k}$ is at $pasympfraclognn$. Here we verify this for $kleqClogn$ with any fixed $C>0$. In a companion paper, using very different methods, we treat the complementary range, proving the conjecture for $kgeqkapp{a}_{0}logn$ (with $kapp{a}_{0}approx4.82$).

Recommendations

• On an anti-Ramsey threshold for random graphs
• Sharp thresholds for certain Ramsey properties of random graphs
• Threshold graph limits and random threshold graphs
• Analytic combinatorics on random graphs
• Random threshold digraphs
• On Some Combinatorial Properties of Random Intersection Graphs
• Betti numbers and anti-lecture Hall compositions of random threshold graphs
• Chromatic thresholds in dense random graphs

Cites work

• Cycle factors and renewal theory
• Embedding nearly-spanning bounded degree trees
• Embedding spanning trees in random graphs
• scientific article; zbMATH DE number 3198427 (Why is no real title available?)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Random Trees in Random Graphs
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Thresholds and Expectation Thresholds

Cited in

(8)

• Betti numbers and anti-lecture Hall compositions of random threshold graphs
• Analytic combinatorics on random graphs
• Spanning structures and universality in sparse hypergraphs
• Cycle factors and renewal theory
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
• Rolling backwards can move you forward: on embedding problems in sparse expanders
• Spanning Trees at the Connectivity Threshold
• scientific article; zbMATH DE number 7650133 (Why is no real title available?)

This page was built for publication: The threshold for combs in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5740276)