ACO The ACO Seminar (2014–2015)

Oct. 9, 3:30pm, Wean 8220
Humberto Naves, Institute for Mathematics and its Applications, University of Minnesota
The threshold probability for long cycles


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). 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 Gp 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.

Back to the ACO home page