 |
The Non-Backtracking Spectrum of the Universal Cover of a Graph
- Postscript version.
- Dvi version.
- PDF version.
-
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 $\sqrt\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 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.
|