
The NonBacktracking Spectrum of the Universal Cover of a Graph
 Postscript version.
 Dvi version.
 PDF version.

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 $\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 nonbacktracking new spectrum near
that of $H$'s universal cover. This suggests a new generalization of
Alon's second eigenvalue conjecture.
