The threshold probability for long cycles

DOI10.1017/S0963548316000237MaRDI QIDQ5366938zbMATH OpenFDO

Authors Roman Glebov, Humberto Naves, Benny 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

binomial random graphHamilton cycle

Mathematics Subject Classification ID

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

Abstract: For a given graph $G$ of minimum degree at least $k$, let $G_p$ denote the random spanning subgraph of $G$ obtained by retaining each edge independently with probability $p=p(k)$. We prove that if $pgefraclogk+loglogk+omeg{a}_k(1)k$, where $omeg{a}_k(1)$ is any function tending to infinity with $k$, then $G_p$ asymptotically almost surely contains a cycle of length at least $k+1$. When we take $G$ to be the complete graph on $k+1$ vertices, our theorem coincides with the classic result on the threshold probability for the existence of a Hamilton cycle in the binomial random graph.

Recommendations

• Long cycles in random subgraphs of graphs with large minimum degree
• Long paths and cycles in random subgraphs of graphs with large minimum degree
• scientific article; zbMATH DE number 4193709
• Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs
• scientific article; zbMATH DE number 3916307

Cites work

• Graph theory
• Hamiltonian circuits in random graphs
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3549021 (Why is no real title available?)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Long cycles in random subgraphs of graphs with large minimum degree
• Long paths and cycles in random subgraphs of graphs with large minimum degree
• On the Number of Hamilton Cycles in Sparse Random Graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• Paths in graphs
• Random Graphs
• The phase transition in random graphs: a simple proof
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(15)

• Paths and cycles in random subgraphs of graphs with large minimum degree
• Large cycles in random generalized Johnson graphs
• A note on spanning \(K_r\)-cycles in random graphs
• Phase transition of degeneracy in minor-closed families
• scientific article; zbMATH DE number 5291597 (Why is no real title available?)
• Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs
• On the probability that a random subgraph contains a circuit
• Long paths and cycles in random subgraphs of graphs with large minimum degree
• On Hamilton cycles in Erdős-Rényi subgraphs of large graphs
• scientific article; zbMATH DE number 4193709 (Why is no real title available?)
• Long cycles in random subgraphs of graphs with large minimum degree
• 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
• Spanning F-cycles in random graphs

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: The threshold probability for long cycles

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