  
  
Stat 
Members: 3658 Articles: 2'599'751 Articles rated: 2609
03 November 2024 

   

Article overview
 

The NonBacktracking Spectrum of the Universal Cover of a Graph  Omer Angel
; Joel Friedman
; Shlomo Hoory
;  Date: 
2 Dec 2007  Abstract:  A nonbacktracking 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 nonbacktracking 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 nonbacktracking walk operator on the
tree covering a finite graph is exactly $sqrtgr$, 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 cite{ST}. Finally,
we give experimental evidence that for a fixed, finite graph, $H$, a random
lift of large degree has nonbacktracking new spectrum near that of $H$’s
universal cover. This suggests a new generalization of Alon’s second eigenvalue
conjecture.  Source:  arXiv, 0712.0192  Services:  Forum  Review  PDF  Favorites 


No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.

 


