The Non-Backtracking Spectrum of the Universal Cover of a Graph

Details The Non-Backtracking Spectrum of the Universal Cover of a Graph The Non-Backtracking Spectrum of the Universal Cover of a Graph

2007-12-02

arxiv.org/abs/0712.0192v1

Mathematics

Combinatorics

Scientific paper

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 \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.

Affiliated with

Also associated with

No associations

Rating

The Non-Backtracking Spectrum of the Universal Cover of a Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Non-Backtracking Spectrum of the Universal Cover of a Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Non-Backtracking Spectrum of the Universal Cover of a Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-50316