BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Probability
SUMMARY:Mixing time for the non-babktracking random walk o
n random graphs with communities - Anna Ben-Hamou
(Paris)
DTSTART;TZID=Europe/London:20181023T140000
DTEND;TZID=Europe/London:20181023T150000
UID:TALK110431AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/110431
DESCRIPTION:The mixing time of random walks on finite connecte
d graphs is tightly related to the existence of bo
ttlenecks in the graph: intuitively\, the harder i
t is for the walk to escape some sets\, the larger
its mixing time. Moreover\, strong bottlenecks us
ually prevent cutoff\, which describes an abrupt c
onvergence to equilibrium. In this talk\, we will
be interested in the mixing behavior of the non-ba
cktracking random walk (NBRW) on random graphs wit
h given degrees and with a two-community structure
. Such graphs have a bottleneck\, whose strength c
an be measured by the fraction of edges that go fr
om one community to the other. Under some degree a
ssumptions\, we will show that\, as long as this f
raction decays more slowly than 1/log(N)\, where N
is the size of the graph\, the NBRW has cutoff\,
and the distance profile can be very precisely des
cribed. On the other hand\, if the fraction decays
faster than 1/log(N)\, then there is no cutoff.
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0W
B
CONTACT:Perla Sousi
END:VEVENT
END:VCALENDAR