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.