The non-backtracking spectrum of the universal cover of a graph
Top Cited Papers
- 3 December 2014
- journal article
- Published by American Mathematical Society (AMS) in Transactions of the American Mathematical Society
- Vol. 367 (6) , 4287-4318
Abstract
A non-backtracking walk on a graph, H H , is a directed path of directed edges of H H such that no edge is the inverse of its preceding edge. Non-backtracking walks of a given length can be counted using the non-backtracking adjacency matrix, B B , indexed by H H ’s directed edges and related to Ihara’s Zeta function. We show how to determine B B ’s spectrum in the case where H H is a tree covering a finite graph. We show that when H H is not regular, this spectrum can have positive measure in the complex plane, unlike the regular case. We show that outside of B B ’s spectrum, the corresponding Green function has “periodic decay ratios”. The existence of such a “ratio system” can be effectively checked and is equivalent to being outside the spectrum. We also prove that the spectral radius of the non-backtracking walk operator on the tree covering a finite graph is exactly g r \sqrt {\mathrm {gr}} , where g r \mathrm {gr} is the cogrowth of B B , or growth rate of the tree. This further motivates the definition of the graph theoretical Riemann hypothesis proposed by Stark and Terras. Finally, we give experimental evidence that for a fixed, finite graph, H H , a random lift of large degree has non-backtracking new spectrum near that of H H ’s universal cover. This suggests a new generalization of Alon’s second eigenvalue conjecture.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- A proof of Alon’s second eigenvalue conjecture and related problemsMemoirs of the American Mathematical Society, 2008
- Non-Backtracking Random Walks and Cogrowth of GraphsCanadian Journal of Mathematics, 2007
- Relative expanders or weakly relatively Ramanujan graphsDuke Mathematical Journal, 2003
- Harmonic analysis for anisotropic random walks on homogeneous treesMemoirs of the American Mathematical Society, 1994
- Cogrowth of Regular GraphsProceedings of the American Mathematical Society, 1992
- On the second eigenvalue and random walks in randomd-regular graphsCombinatorica, 1991
- Algebraic equations for Green kernel on a treeProceedings of the Japan Academy, Series A, Mathematical Sciences, 1988
- A formula of eigen-function expansions I. Case of asymptotic treesProceedings of the Japan Academy, Series A, Mathematical Sciences, 1985
- Cogrowth of groups and simple random walksArchiv der Mathematik, 1983
- Low-density parity-check codesIEEE Transactions on Information Theory, 1962