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?)

  • [1] 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 (2008k:60017),
  • [2] Noga Alon, Shlomo Hoory, and Nathan Linial, The Moore bound for irregular graphs, Graphs Combin. 18 (2002), no. 1, 53-57. MR 1892433 (2003b:05084),
  • [3] 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 (86m:58127)
  • [4] 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 (86m:22009)
  • [5] 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 (90a:47072)
  • [6] K. Aomoto, Point spectrum on a quasihomogeneous tree, Pacific J. Math. 147 (1991), no. 2, 231-242. MR 1084706 (92g:47042)
  • [7] Laurent Bartholdi, Counting paths in graphs, Enseign. Math. (2) 45 (1999), no. 1-2, 83-131. MR 1703364 (2000f:05047)
  • [8] Hyman Bass, The Ihara-Selberg zeta function of a tree lattice, Internat. J. Math. 3 (1992), no. 6, 717-797. MR 1194071 (94a:11072),
  • [9] 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.
  • [10] 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 (95a:22003),
  • [11] Joel Friedman, On the second eigenvalue and random walks in random $ d$-regular graphs, Combinatorica 11 (1991), no. 4, 331-362. MR 1137767 (93i:05115),
  • [12] Joel Friedman, Some geometric aspects of graphs and their eigenfunctions, Duke Math. J. 69 (1993), no. 3, 487-525. MR 1208809 (94b:05134),
  • [13] Joel Friedman, Relative expanders or weakly relatively Ramanujan graphs, Duke Math. J. 118 (2003), no. 1, 19-35. MR 1978881 (2004m:05165),
  • [14] 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 (2010e:05181),
  • [15] Joel Friedman and David Kohler, On the relativized Alon conjecture, to appear.
  • [16] 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 (2005k:05142),
  • [17] R. G. Gallager, Low-density parity-check codes, IRE Trans. IT-8 (1962), 21-28. MR 0136009 (24 #B2048)
  • [18] 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 (83k:60016)
  • [19] 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 (91i:11057)
  • [20] 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 (2010a:35028),
  • [21] 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 (2005k:05144),
  • [22] Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439-561 (electronic). MR 2247919 (2007h:68055),
  • [23] Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183 (87e:15001)
  • [24] 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,
  • [25] 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,
  • [26] Motoko Kotani and Toshikazu Sunada, Zeta functions of finite graphs, J. Math. Sci. Univ. Tokyo 7 (2000), no. 1, 7-25. MR 1749978 (2001f:68110)
  • [27] S. Northshield, Cogrowth of regular graphs, Proc. Amer. Math. Soc. 116 (1992), no. 1, 203-205. MR 1120509 (93e:60143),
  • [28] Ronald Ortner and Wolfgang Woess, Non-backtracking random walks and cogrowth of graphs, Canad. J. Math. 59 (2007), no. 4, 828-844. MR 2338235 (2008h:05057),
  • [29] Tom Richardson and Rüdiger Urbanke, Modern coding theory, Cambridge University Press, Cambridge, 2008. MR 2494807 (2010i:94004)
  • [30] Walter Rudin, Functional analysis, 2nd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Inc., New York, 1991. MR 1157815 (92k:46001)
  • [31] 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 (2005d:94210)
  • [32] H. M. Stark and A. A. Terras, Zeta functions of finite graphs and coverings. III, Adv. Math. 208 (2007), no. 1, 467-489. MR 2304325 (2009c:05103),
  • [33] Wolfgang Woess, Cogrowth of groups and simple random walks, Arch. Math. (Basel) 41 (1983), no. 4, 363-370. MR 731608 (86h:60133),

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

Joel Friedman
Affiliation: Department of Computer Science, University of British Columbia, Vancouver, British Columbia, Canada V6T 1Z2

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

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

American Mathematical Society