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 +
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