About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Trans. Am. Math. Soc.
Paper
The non-backtracking spectrum of the universal cover of a graph
Abstract
A non-backtracking walk on a graph, H, is a directed path of directed edges of H such that no edge is the inverse of its preceding edge. Nonbacktracking walks of a given length can be counted using the non-backtracking adjacency matrix, B, indexed by H’s directed edges and related to Ihara’s Zeta function. We show how to determine B’s spectrum in the case where H is a tree covering a finite graph. We show that when H is not regular, this spectrum can have positive measure in the complex plane, unlike the regular case. We show that outside of 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 √ gr, where gr is the cogrowth of 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, a random lift of large degree has non-backtracking new spectrum near that of H’s universal cover. This suggests a new generalization of Alon’s second eigenvalue conjecture.