Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3658
Articles: 2'599'751
Articles rated: 2609

03 November 2024
 
  » arxiv » 0712.0192

 Article overview



The Non-Backtracking Spectrum of the Universal Cover of a Graph
Omer Angel ; Joel Friedman ; Shlomo Hoory ;
Date 2 Dec 2007
AbstractA 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 $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 non-backtracking 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   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  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.






ScienXe.org
» my Online CV
» Free

home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica