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
DOI: https://doi.org/10.1090/S0002-9947-2014-06255-7
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), https://doi.org/10.1142/S0219199707002551
  • [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), https://doi.org/10.1007/s003730200002
  • [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), https://doi.org/10.1142/S0129167X92000357
  • [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), https://doi.org/10.1090/memo/0531
  • [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), https://doi.org/10.1007/BF01275669
  • [12] Joel Friedman, Some geometric aspects of graphs and their eigenfunctions, Duke Math. J. 69 (1993), no. 3, 487-525. MR 1208809 (94b:05134), https://doi.org/10.1215/S0012-7094-93-06921-9
  • [13] Joel Friedman, Relative expanders or weakly relatively Ramanujan graphs, Duke Math. J. 118 (2003), no. 1, 19-35. MR 1978881 (2004m:05165), https://doi.org/10.1215/S0012-7094-03-11812-8
  • [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), https://doi.org/10.1090/memo/0910
  • [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), https://doi.org/10.2140/pjm.2004.216.229
  • [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), https://doi.org/10.1016/j.ejc.2008.03.008
  • [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), https://doi.org/10.1016/j.jctb.2004.06.001
  • [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), https://doi.org/10.1090/S0273-0979-06-01126-8
  • [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, https://doi.org/10.1007/s11854-012-0040-4
  • [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, https://doi.org/10.1007/s11856-012-0059-3
  • [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), https://doi.org/10.2307/2159315
  • [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), https://doi.org/10.4153/CJM-2007-035-1
  • [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), https://doi.org/10.1016/j.aim.2006.03.002
  • [33] Wolfgang Woess, Cogrowth of groups and simple random walks, Arch. Math. (Basel) 41 (1983), no. 4, 363-370. MR 731608 (86h:60133), https://doi.org/10.1007/BF01371408

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

American Mathematical Society