BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Mixing time for the non-babktracking random walk on random graphs 
 with communities - Anna Ben-Hamou (Paris)
DTSTART:20181023T130000Z
DTEND:20181023T140000Z
UID:TALK110431@talks.cam.ac.uk
CONTACT:Perla Sousi
DESCRIPTION:The mixing time of random walks on finite connected graphs is 
 tightly related to the existence of bottlenecks in the graph: intuitively\
 , the harder it is for the walk to escape some sets\, the larger its mixin
 g time. Moreover\, strong bottlenecks usually prevent cutoff\, which descr
 ibes an abrupt convergence to equilibrium. In this talk\, we will be inter
 ested in the mixing behavior of the non-backtracking random walk (NBRW) on
  random graphs with given degrees and with a two-community structure. Such
  graphs have a bottleneck\, whose strength can be measured by the fraction
  of edges that go from one community to the other. Under some degree assum
 ptions\, we will show that\, as long as this fraction decays more slowly t
 han 1/log(N)\, where N is the size of the graph\, the NBRW has cutoff\, an
 d the distance profile can be very precisely described. 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 0WB
END:VEVENT
END:VCALENDAR