Fri, 25 Apr 2008
14:00
14:00
L3
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.