Forthcoming events in this series


Tue, 11 Nov 2003
15:00
L3

The Evolution of the Mixing Rate

Bruce Reed
(McGill University)
Abstract

We will discuss the mixing rate of the standard random walk on the giant

component of the random graph G(n,p). We tie down the mixing rate precisely

for all values of p greater than (1+c)/n for any positive constant c. We need

to develop a new bound on the mixing time of general Markov chains, inspired

by and extending work of Kannan and Lovasz. This is joint work with Nick

Fountoulakis.