Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

   
 

 

The non-backtracking spectrum of the universal cover of a graph


Authors: Omer Angel, Joel Friedman and Shlomo Hoory
Journal: Trans. Amer. Math. Soc. 367 (2015), 4287-4318
MSC (2010): Primary 05C50; Secondary 05C80
Published electronically: December 3, 2014
MathSciNet review: 3324928
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 \mathrm {gr}$, where $ \mathrm {gr}$ is the cogrowth of $ B$, or growth rate of the tree. This further motivates the definition of the graph theoretical Riemann hypothesis proposed by Stark and Terras.

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C50, 05C80

Retrieve articles in all journals with MSC (2010): 05C50, 05C80


Additional Information

Omer Angel
Affiliation: Department of Mathematics, University of British Columbia, Vancouver, British Columbia, Canada V6T 1Z2
Email: angel@math.ubc.ca

Joel Friedman
Affiliation: Department of Computer Science, University of British Columbia, Vancouver, British Columbia, Canada V6T 1Z2
Email: jf@cs.ubc.ca

Shlomo Hoory
Affiliation: Haifa Research Laboratory, IBM, 31905 Haifa, Israel
Address at time of publication: Qualcomm, 10 Haagas St., P.O.B. 1935, 37808 Givaat Ada, Israel
Email: shlomoh@il.ibm.com, hoorys@gmail.com

DOI: https://doi.org/10.1090/S0002-9947-2014-06255-7
Received by editor(s): April 26, 2012
Received by editor(s) in revised form: April 25, 2013, and July 20, 2013
Published electronically: December 3, 2014
Additional Notes: This research was done while the first and third authors were at the University of British Columbia; the first held a PIMS postdoctoral fellowship.
Article copyright: © Copyright 2014 by Omer Angel, Joel Friedman, and Shlomo Hoory