Discrete Mathematics and Optimization Seminar

---

NIKOLAOS FOUNTOULAKIS
McGill University
Monday October 20th at 4.30pm
Burnside 1205



Title. The mixing time of a random walk on a random graph.

Abstract. We estimate the mixing time of the standard random walk on the largest component of a sparse random graph. To achieve
this, we present a new upper bound on the mixing time of an aperiodic Markov chain on a graph, which requires a new definition
of the notion of conductance. We apply this bound determining the (newly defined) conductance of the largest component of a
sparse random graph. (This is joint work with B.A. Reed.)