BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/213
DTSTAMP:20230914T125915Z
SUMMARY:Random Regular Graphs: Generation and Cover Time
DESCRIPTION:Speaker: Mohit Garg\nTata Institute of Fundamental Research\nSc
hool of Technology and Computer Science\nHomi Bhabha Road\n\nAbstract: \nA
graph is $r$-regular if all its vertices have the same degree $r$. A rand
om $r$-regular graph with $n$ vertices is a graph sampled uniformly at ran
dom from the set of all $r$-regular graphs on $n$ vertices. There are vari
ous sampling methods for this. In this talk we look at one of them: The Co
nfiguration 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 C
olin Cooper and Alan Frieze\, uses generating function technique and resul
ts from complex analysis\, which we illustrate in this talk.\n\n(Key words
.) Random regular graphs\, configuration model\, cover time\, combinatoric
s.\n
URL:https://www.tcs.tifr.res.in/web/events/213
DTSTART;VALUE=DATE:20110803
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR