The Threshold Probability for Long Cycles
Open Access
- 8 September 2016
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 26 (2) , 208-247
Abstract
For a given graph G of minimum degree at least k, let Gp denote the random spanning subgraph of G obtained by retaining each edge independently with probability p = p(k). We prove that if p ⩾ (logk + loglogk + ωk(1))/k, where ωk(1) is any function tending to infinity with k, then Gp 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.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Long cycles in random subgraphs of graphs with large minimum degreeRandom Structures & Algorithms, 2014
- Long paths and cycles in random subgraphs of graphs with large minimum degreeRandom Structures & Algorithms, 2013
- On the Number of Hamilton Cycles in Sparse Random GraphsSIAM Journal on Discrete Mathematics, 2013
- The phase transition in random graphs: A simple proofRandom Structures & Algorithms, 2012
- On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random GraphsSIAM Journal on Discrete Mathematics, 2011
- Random Graphs2001
- Limit distribution for the existence of hamiltonian cycles in a random graphDiscrete Mathematics, 1983
- Hamiltonian circuits in random graphsDiscrete Mathematics, 1976
- Random GraphsThe Annals of Mathematical Statistics, 1959
- Zur allgemeinen KurventheorieFundamenta Mathematicae, 1927