The ACO Seminar (2014–2015)

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). In this talk, we prove that if p ≥ (log k + log log k + ω_k(1))/k, where ω_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 G is 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.