| | |
| | |
Stat |
Members: 3658 Articles: 2'599'751 Articles rated: 2609
03 November 2024 |
|
| | | |
|
Article overview
| |
|
The Non-Backtracking Spectrum of the Universal Cover of a Graph | Omer Angel
; Joel Friedman
; Shlomo Hoory
; | Date: |
2 Dec 2007 | 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. 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 |
|
|
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.
|
| |
|
|
|