The threshold for combs in random graphs

DOI10.1002/rsa.20614zbMath1341.05231arXiv1401.2710OpenAlexW1671329496MaRDI QIDQ5740276

Eyal Lubetzky, Nicholas C. Wormald, Jeffry Kahn

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) Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38)

Related Items

Rolling backwards can move you forward: On embedding problems in sparse expanders, Spanning Trees at the Connectivity Threshold, 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

Cites Work

• Unnamed Item
• Embedding nearly-spanning bounded degree trees
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Cycle Factors and Renewal Theory
• Embedding Spanning Trees in Random Graphs
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Thresholds and Expectation Thresholds
• Random Trees in Random Graphs