Tata Institute of Fundamental Research
Random Regular Graphs: Generation and Cover Time
Project Seminar
Speaker:
Mohit Garg
Tata Institute of Fundamental Research
School of Technology and Computer Science
Homi Bhabha Road
Date:
Wednesday, 3 Aug 2011 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
A graph is $r$-regular if all its vertices have the same degree $r$. A random $r$-regular graph with $n$ vertices is a graph sampled uniformly at random from the set of all $r$-regular graphs on $n$ vertices. There are various sampling methods for this. In this talk we look at one of them: The Configuration Model. We then look at the cover time of a random walk on such a graph, which roughly speaking, is the time taken (in expectation) by the walk to visit all the vertices. This cover time calculation, due to Colin Cooper and Alan Frieze, uses generating function technique and results from complex analysis, which we illustrate in this talk.
(Key words.) Random regular graphs, configuration model, cover time, combinatorics.
| Speaker: | Mohit Garg Tata Institute of Fundamental Research School of Technology and Computer Science Homi Bhabha Road |
| Date: | Wednesday, 3 Aug 2011 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
A graph is $r$-regular if all its vertices have the same degree $r$. A random $r$-regular graph with $n$ vertices is a graph sampled uniformly at random from the set of all $r$-regular graphs on $n$ vertices. There are various sampling methods for this. In this talk we look at one of them: The Configuration Model. We then look at the cover time of a random walk on such a graph, which roughly speaking, is the time taken (in expectation) by the walk to visit all the vertices. This cover time calculation, due to Colin Cooper and Alan Frieze, uses generating function technique and results from complex analysis, which we illustrate in this talk.
(Key words.) Random regular graphs, configuration model, cover time, combinatorics.
(Key words.) Random regular graphs, configuration model, cover time, combinatorics.