Computer Science/Discrete Mathematics Seminar I

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.