Oct. 9, 3:30pm, Wean 8220

Humberto Naves, Institute for Mathematics and its Applications, University of Minnesota

The threshold probability for long cycles

Humberto Naves, Institute for Mathematics and its Applications, University of Minnesota

The threshold probability for long cycles

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