Some relations between the spectra of simple and non-backtracking random walks

arXiv1703.03852MaRDI QIDQ6284193FDOQ6284193

Authors: Nalini Anantharaman 

Publication date: 9 March 2017

Abstract: We establish some relations between the spectra of simple and non-backtracking random walks on non-regular graphs, generalizing some well-known facts for regular graphs. Our two main results are 1) a quantitative relation between the mixing rates of the simple random walk and of the non-backtracking random walk 2) a variant of the "Ihara determinant formula" which expresses the characteristic polynomial of the adjacency matrix, or of the laplacian, as the determinant of a certain non-backtracking random walk with holomorphic weights.

This page was built for publication: Some relations between the spectra of simple and non-backtracking random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284193)