THE NON-BACKTRACKING SPECTRUM OF THE UNIVERSAL COVER OF A GRAPH

By Omer Angel, Joel Friedman, Shlomo Hoory. 2007

109 citations recorded by the source corpus.

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. Non-backtracking 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 growth rate of the tree. This further motivates the definition of the graph theoretical Riemann hypothesis proposed by Stark and Terras (ST). Finally, we give experimental evidence that for a fixed, finite graph, H, a ran- dom 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.

Subfields: Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/2c6cae3d2dab161c10a1ff68ce238507d8c9e883

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Electrical and Electronic Engineering

In Geometry and Topology

Citations in the corpus

Cutoff on all Ramanujan graphs (2015, background): “that appear implicitly in [20] (see also [5,7,8] as well as [26, Exercise 6.”
A new proof of Friedman's second eigenvalue theorem and its extension to random lifts (2015, background): “Also, coming back to Theorem 19, Angel, Friedman and Hoory [5] proved that √ ρ1 is the spectral radius of the non-backtracking operator of T , the universal covering tree of X.”
Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs (2018, background): “If G is connected, λ1(B) is equal to the growth rate of the universal cover of G (see Angel, Friedman and Hoory [1]).”
Community detection in networks: A user guide (2016, background): “A non-backtracking walk [126] is a path across the edges of a graph that is allowed to return to a vertex visited previously only after at least two other vertices have been visited; immediate returns like 1 → 2 → 1 are forbidden.”
Cutoff phenomena for random walks on random regular graphs (2008, background): “Alternatively, if the random walk is not on C, then it moves one step closer to C with probability 1d and one step further away with probability d−1 d .”
Non-backtracking random walks and a weighted Ihara's theorem (2016, background): “Recently, Angel, Friedman, and Hoory [2] studied non-backtracking walks on the universal cover of a graph.”