# zbMATH — the first resource for mathematics

Cutoff for nonbacktracking random walks on sparse random graphs. (English) Zbl 1372.60101
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.

##### MSC:
 60J10 Markov chains (discrete-time Markov processes on discrete state spaces) 05C81 Random walks on graphs 60G50 Sums of independent random variables; random walks 05C80 Random graphs (graph-theoretic aspects)
##### Keywords:
cutoff; nonbacktracking random walk; random graph
Full Text: