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

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.

• Speaker: Anna Ben-Hamou (Paris)
• Tuesday 23 October 2018, 14:00–15:00
• Venue: MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB.
• Series: Probability; organiser: Perla Sousi.