Cutoff and mixing trichotomy for the simple random walk on random digraphs

Link to Join MS Teams Talk

This talk will be broadcast at 13:30 GMT / 14:30 CET / 15:30 EET, April 30th, 2025 on MS Teams only.

Meeting ID: 393 527 089 878
Passcode: dsm7py

Abstract

We study the mixing behaviour of the simple random walk on two different random digraphs (directed graphs). We first consider the Chung-Lu digraph, which belongs to the family of inhomogeneous Erdős–Rényi digraphs, in a weakly dense regime where the random walk is irreducible. As the size n of the graph grows, the model exhibits with high probability a cutoff with a Gaussian window, namely an abrupt decay of the distance to equilibrium, at the threshold timescale log n/ log log n. We then introduce a digraph featuring a community structure, inspired by the stochastic block model. This second environment provides a mixing trichotomy, depending on the strength of connectivity among communities: we identify a subcritical regime, in which cutoff occurs; a supercritical regime, where the system has a sort of metastable behaviour; a critical regime, with mixed behaviour. We provide a characterization in terms of limit profiles, which enriches the analysis performed in the reversible setting.

Joint works with Alessandra Bianchi and Matteo Quattropani.

About Giacomo

Giacomo is currently a third year PhD student at the University of Padova under the supervision of Alessandra Bianchi. His research interests involve mixing times of random dynamics and random graphs.