Mixing time for the non-babktracking random walk on random graphs with communities

Add to your list(s) Download to your calendar using vCal

• Anna Ben-Hamou (Paris)
• Tuesday 23 October 2018, 14:00-15:00
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB.

If you have a question about this talk, please contact Perla Sousi.

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 mixing time. Moreover, strong bottlenecks usually prevent cutoff, which describes an abrupt convergence to equilibrium. In this talk, we will be interested 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 assumptions, we will show that, as long as this fraction 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 described. On the other hand, if the fraction decays faster than 1/log(N), then there is no cutoff.

This talk is part of the Probability series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB
• Probability
• School of Physical Sciences
• Statistical Laboratory info aggregator
• bld31

Note that ex-directory lists are not shown.