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.