Cutoff for nonbacktracking random walks on sparse random graphs (Q2012250)

Based on a given vertex set \(V\) and a function deg: \(V\to \{2,3,\ldots \}\) \((N:=\sum_{v\in V}\text{deg}(v))\), one constructs a graph attaching deg(\(v\)) half-edges to each vertex \(v\in V\) \[ \mathcal{X}:=\{(v,i):v\in V,1\leq i\leq \text{deg}(v)\}. \] One chooses a pairing \(\pi \) on \(V\) and interprets every pair of matched half-edges \(\{x,\pi (x)\}\) as an edge between the corresponding vertices. The nonbacktracking random walk (NBRW) is a discrete-time Markov chain where the transitions to the neighbouring vertices are possible with uniform distribution. The paper studies the sparse regime where the number \(N\) of half-edges diverges at a faster rate than the maximum degree. The main result states the NBRW shows the so-called cutoff phenomenon, the distance to equilibrium remains close to 1 for a long time and then drops to 0 over a much shorter time scale, the cutoff shape approaches the tail distribution of the standard nomal distribution.