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.