abstract
COMPUTER SCIENCE/DISCRETE MATH I | |
Topic: | The Cover Time of Random Walks on Random Graphs |
Speaker: | Alan Frieze |
Affiliation: | Carnegie Mellon University |
Date: | Monday, March 27 |
Time/Room: | 11:15am - 12:15pm/S-101 |
We give asymptotically precise estimates for the expected time taken for a random walk to visit all vertices of a graph, viz. the cover time. We do this for several models of random graphs viz. $G_{n,p}$ when $p$ is above the connectivity threshold; random $r$-regular graphs; the giant component of $G_{n,p)$ when the average degree is a constant larger than 1; the preferential attachment graph. The results are based on a lemma that can most usefully be applied to graphs of "high girth" and for which the random walk is "rapidly mixing" e.g. Ramanujan graphs.