The Threshold Probability for Long Cycles

DOI10.1017/S0963548316000237zbMath1371.05269arXiv1408.4332MaRDI QIDQ5366938

Humberto Naves, Roman Glebov, Benjamin Sudakov

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

Hamilton cyclebinomial random graph

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Vertex degrees (05C07) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (6)

Large complete minors in random subgraphs ⋮ Perfect matchings in random subgraphs of regular bipartite graphs ⋮ Long paths in heterogeneous random subgraphs of graphs with large minimum degree ⋮ Phase transition of degeneracy in minor-closed families ⋮ On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs ⋮ Paths and cycles in random subgraphs of graphs with large minimum degree

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Hamiltonian circuits in random graphs
• The phase transition in random graphs: A simple proof
• On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random Graphs
• Paths in graphs
• Long paths and cycles in random subgraphs of graphs with large minimum degree
• Long cycles in random subgraphs of graphs with large minimum degree
• On the Number of Hamilton Cycles in Sparse Random Graphs
• Random Graphs

This page was built for publication: The Threshold Probability for Long Cycles