The non-backtracking spectrum of the universal cover of a graph
HTML articles powered by AMS MathViewer
- by Omer Angel, Joel Friedman and Shlomo Hoory PDF
- Trans. Amer. Math. Soc. 367 (2015), 4287-4318
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
- Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin, Non-backtracking random walks mix faster, Commun. Contemp. Math. 9 (2007), no. 4, 585–603. MR 2348845, DOI 10.1142/S0219199707002551
- Noga Alon, Shlomo Hoory, and Nathan Linial, The Moore bound for irregular graphs, Graphs Combin. 18 (2002), no. 1, 53–57. MR 1892433, DOI 10.1007/s003730200002
- Kazuhiko Aomoto, Spectral theory on a free group and algebraic curves, J. Fac. Sci. Univ. Tokyo Sect. IA Math. 31 (1984), no. 2, 297–318. MR 763424
- Kazuhiko Aomoto, A formula of eigenfunction expansions. I. Case of asymptotic trees, Proc. Japan Acad. Ser. A Math. Sci. 61 (1985), no. 1, 11–14. MR 798026
- Kazuhiko Aomoto, Algebraic equations for Green kernel on a tree, Proc. Japan Acad. Ser. A Math. Sci. 64 (1988), no. 4, 123–125. MR 966404
- K. Aomoto, Point spectrum on a quasihomogeneous tree, Pacific J. Math. 147 (1991), no. 2, 231–242. MR 1084706
- Laurent Bartholdi, Counting paths in graphs, Enseign. Math. (2) 45 (1999), no. 1-2, 83–131. MR 1703364
- Hyman Bass, The Ihara-Selberg zeta function of a tree lattice, Internat. J. Math. 3 (1992), no. 6, 717–797. MR 1194071, DOI 10.1142/S0129167X92000357
- A. Broder and E. Shamir, On the second eigenvalue of random regular graphs, The 28th Annual Symposium on Foundations of Computer Science, 1987, pp. 286–294.
- Alessandro Figà-Talamanca and Tim Steger, Harmonic analysis for anisotropic random walks on homogeneous trees, Mem. Amer. Math. Soc. 110 (1994), no. 531, xii+68. MR 1219707, DOI 10.1090/memo/0531
- Joel Friedman, On the second eigenvalue and random walks in random $d$-regular graphs, Combinatorica 11 (1991), no. 4, 331–362. MR 1137767, DOI 10.1007/BF01275669
- Joel Friedman, Some geometric aspects of graphs and their eigenfunctions, Duke Math. J. 69 (1993), no. 3, 487–525. MR 1208809, DOI 10.1215/S0012-7094-93-06921-9
- Joel Friedman, Relative expanders or weakly relatively Ramanujan graphs, Duke Math. J. 118 (2003), no. 1, 19–35. MR 1978881, DOI 10.1215/S0012-7094-03-11812-8
- Joel Friedman, A proof of Alon’s second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc. 195 (2008), no. 910, viii+100. MR 2437174, DOI 10.1090/memo/0910
- Joel Friedman and David Kohler, On the relativized Alon conjecture, to appear.
- Joel Friedman and Jean-Pierre Tillich, Wave equations for graphs and the edge-based Laplacian, Pacific J. Math. 216 (2004), no. 2, 229–266. MR 2094545, DOI 10.2140/pjm.2004.216.229
- R. G. Gallager, Low-density parity-check codes, IRE Trans. IT-8 (1962), 21–28. MR 0136009, DOI 10.1109/tit.1962.1057683
- R. I. Grigorchuk, Symmetrical random walks on discrete groups, Multicomponent random systems, Adv. Probab. Related Topics, vol. 6, Dekker, New York, 1980, pp. 285–325. MR 599539
- Ki-ichiro Hashimoto, Zeta functions of finite graphs and representations of $p$-adic groups, Automorphic forms and geometry of arithmetic varieties, Adv. Stud. Pure Math., vol. 15, Academic Press, Boston, MA, 1989, pp. 211–280. MR 1040609, DOI 10.2969/aspm/01510211
- Yusuke Higuchi and Yuji Nomura, Spectral structure of the Laplacian on a covering graph, European J. Combin. 30 (2009), no. 2, 570–585. MR 2489251, DOI 10.1016/j.ejc.2008.03.008
- Shlomo Hoory, A lower bound on the spectral radius of the universal cover of a graph, J. Combin. Theory Ser. B 93 (2005), no. 1, 33–43. MR 2102266, DOI 10.1016/j.jctb.2004.06.001
- Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561. MR 2247919, DOI 10.1090/S0273-0979-06-01126-8
- Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183, DOI 10.1017/CBO9780511810817
- Matthias Keller, Daniel Lenz, and Simone Warzel, Absolutely continuous spectrum for random operators on trees of finite cone type, J. Anal. Math. 118 (2012), no. 1, 363–396. MR 3070682, DOI 10.1007/s11854-012-0040-4
- Matthias Keller, Daniel Lenz, and Simone Warzel, On the spectral theory of trees with finite cone type, Israel J. Math. 194 (2013), no. 1, 107–135. MR 3047064, DOI 10.1007/s11856-012-0059-3
- Motoko Kotani and Toshikazu Sunada, Zeta functions of finite graphs, J. Math. Sci. Univ. Tokyo 7 (2000), no. 1, 7–25. MR 1749978
- S. Northshield, Cogrowth of regular graphs, Proc. Amer. Math. Soc. 116 (1992), no. 1, 203–205. MR 1120509, DOI 10.1090/S0002-9939-1992-1120509-0
- Ronald Ortner and Wolfgang Woess, Non-backtracking random walks and cogrowth of graphs, Canad. J. Math. 59 (2007), no. 4, 828–844. MR 2338235, DOI 10.4153/CJM-2007-035-1
- Tom Richardson and Rüdiger Urbanke, Modern coding theory, Cambridge University Press, Cambridge, 2008. MR 2494807, DOI 10.1017/CBO9780511791338
- Walter Rudin, Functional analysis, 2nd ed., International Series in Pure and Applied Mathematics, McGraw-Hill, Inc., New York, 1991. MR 1157815
- Amin Shokrollahi, LDPC codes: an introduction, Coding, cryptography and combinatorics, Progr. Comput. Sci. Appl. Logic, vol. 23, Birkhäuser, Basel, 2004, pp. 85–110. MR 2090642
- A. A. Terras and H. M. Stark, Zeta functions of finite graphs and coverings. III, Adv. Math. 208 (2007), no. 1, 467–489. MR 2304325, DOI 10.1016/j.aim.2006.03.002
- Wolfgang Woess, Cogrowth of groups and simple random walks, Arch. Math. (Basel) 41 (1983), no. 4, 363–370. MR 731608, DOI 10.1007/BF01371408
Additional Information
- Omer Angel
- Affiliation: Department of Mathematics, University of British Columbia, Vancouver, British Columbia, Canada V6T 1Z2
- MR Author ID: 667585
- Email: angel@math.ubc.ca
- Joel Friedman
- Affiliation: Department of Computer Science, University of British Columbia, Vancouver, British Columbia, Canada V6T 1Z2
- MR Author ID: 207257
- 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
- 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.
- © Copyright 2014 by Omer Angel, Joel Friedman, and Shlomo Hoory
- Journal: Trans. Amer. Math. Soc. 367 (2015), 4287-4318
- MSC (2010): Primary 05C50; Secondary 05C80
- DOI: https://doi.org/10.1090/S0002-9947-2014-06255-7
- MathSciNet review: 3324928