Random walks on the random graph (Q1747756)

This paper studies the mixing time of simple and non-backtracking random walks on Erdős-Renyi random graphs and random graphs with given degree sequences. Let \(C\) be the giant component of the Erdős-Renyi graph \(G(n,p)\) with \(p=\lambda/n\) and \(\lambda>1\) fixed. Let \(v\) and \(d\) be the speed of a random walk and the dimension of the harmonic measure on a Poisson(\(\lambda\))-Galton-Watson tree, respectively. For any \(\varepsilon\in(0,1)\), the random walk from a uniformly chosen vertex \(w\in C\) satisfies \(|t_{\mathrm{MIX}}(\varepsilon)-(vd)^{-1}\ln n|\leq (\ln n)^{0.5+o(1)}\) with high probability. Moreover, let \(G\) be a random graph on a degree sequence \((d_1,\dots,d_n)\) with \(p_k=\frac1n|\{i:d_i=k\}|\). Define \(Z\) by \(P(Z=k-1)\propto kp_k\). Let \(t^*=(vd)^{-1}\ln n\), where \(v\) and \(d\) are the speed of random walk and dimension of harmonic measure on a Galton-Watson tree with offspring distribution \(Z\). Set \(w_n=\sqrt{\ln n}\) and suppose that for some \(K\) and \(\delta>0\), \(EZ<K\), \(2\leq Z\leq \Delta=\exp((\ln n)^{0.5-\delta})\). For any \(\varepsilon>0\), there exists some \(\gamma>0\) such that if \(n\) is large enough with high probability, \(d_{TV}(t^*-\gamma w_n)>1-\varepsilon\), whereas \(d_{TV}(t^*+\gamma w_n)<\varepsilon\).