COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Probability > Mixing time for the non-babktracking random walk on random graphs with communities

## Mixing time for the non-babktracking random walk on random graphs with communitiesAdd 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
- 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. |
## Other listsAdvances and Controversies in Lipid Lowering Type the title of a new list here SciScreen Cambridge## Other talksEnergy Efficient Cities SciScreen : First Man CAN HIGH TECHNOLOGY PRODUCTS BE SUSTAINABLE? Zone 6 Convention Cities, Skills and Space: Capturing the Unobservable Annual Hopkins Seminar 2018 - Targeted Antisense Therapeutics for Modulation of Splicing or NMD |