Cycle density in infinite Ramanujan graphs. (English) Zbl 1346.60061

Lyons, Russell; Peres, Yuval

Ann. Probab. 43, No. 6, 3337-3358 (2015).

Authors’ abstract: We introduce a technique using nonbacktracking random walks for estimating the spectral radius of simple random walks. This technique relates the density of nontrivial cycles in a simple random walk to that in a nonbacktracking random walk. We apply this to infinite Ramanujan graphs, which are regular graphs whose spectral radius equals that of the tree of the same degree. Kesten showed that the only infinite Ramanujan graphs that are Cayley graphs are trees. This result was extended to unimodular random rooted regular graphs by M. Abért et al., [Ann. Probab. 43, No. 6, 3337–3358 (2015; Zbl 1339.05365)]. We show that an analogous result holds for all regular graphs: the frequency of times spent by a simple random walk in a nontrivial cycle is a.s. 0 on every infinite Ramanujan graph. We also give quantitative versions of that result, which we apply to answer another question of Abért et al. [loc. cit], showing that on an infinite Ramanujan graph, the probability that a simple random walk encounters a short cycle tends to 0 a.s. as the time tends to infinity.

Reviewer: Aleksander Iksanov (Kiev)

MSC:

60G50	Sums of independent random variables; random walks
60F15	Strong limit theorems
05C81	Random walks on graphs
82C41	Dynamics of random walks, random surfaces, lattice animals, etc. in time-dependent statistical mechanics

Keywords:

nonbacktracking random walk; simple random walk; regular graph; spectral radius

Citations:

Zbl 1339.05365

References:

[1]	Abért, M., Glasner, Y. and Virág, B. (2015). The measurable Kesten theorem. Ann. Probab. · Zbl 1339.05365 · doi:10.1214/14-AOP937
[2]	Alon, N. (1986). Eigenvalues and expanders. Combinatorica 6 83-96. Theory of computing (Singer Island, Fla., 1984). · Zbl 0661.05053 · doi:10.1007/BF02579166
[3]	Alon, N., Benjamini, I., Lubetzky, E. and Sodin, S. (2007). Non-backtracking random walks mix faster. Commun. Contemp. Math. 9 585-603. · Zbl 1140.60301 · doi:10.1142/S0219199707002551
[4]	Ancona, A. (1988). Positive harmonic functions and hyperbolicity. In Potential Theory-Surveys and Problems ( Prague , 1987) (J. Král, J. Lukeš, I. Netuka and J. Veselý, eds.). Lecture Notes in Math. 1344 1-23. Springer, Berlin. · Zbl 0883.60010 · doi:10.2307/2951843
[5]	Biggs, N. L., Mohar, B. and Shawe-Taylor, J. (1988). The spectral radius of infinite graphs. Bull. Lond. Math. Soc. 20 116-120. · Zbl 0671.05052 · doi:10.1112/blms/20.2.116
[6]	Cheeger, J. (1970). A lower bound for the smallest eigenvalue of the Laplacian. In Problems in Analysis ( Papers Dedicated to Salomon Bochner , 1969) (R. C. Gunning, ed.) 195-199. Princeton Univ. Press, Princeton, NJ. · Zbl 0212.44903
[7]	Dodziuk, J. (1984). Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Amer. Math. Soc. 284 787-794. · Zbl 0512.39001 · doi:10.2307/1999107
[8]	Dodziuk, J. and Kendall, W. S. (1986). Combinatorial Laplacians and isoperimetric inequality. In From Local Times to Global Geometry , Control and Physics ( Coventry , 1984 / 85) (K. D. Elworthy, ed.). Pitman Res. Notes Math. Ser. 150 68-74. Longman, Harlow. · Zbl 0619.05005
[9]	Gerl, P. (1988). Random walks on graphs with a strong isoperimetric property. J. Theoret. Probab. 1 171-187. · Zbl 0639.60072 · doi:10.1007/BF01046933
[10]	Grigorchuk, R. I. (1980). Symmetrical random walks on discrete groups. In Multicomponent Random Systems (R. L. Dobrushin, Ya. G. Sinaĭ and D. Griffeath, eds.). Adv. Probab. Related Topics 6 285-325. Dekker, New York. · Zbl 0475.60007
[11]	Kaimanovich, V. A. (1992). Dirichlet norms, capacities and generalized isoperimetric inequalities for Markov operators. Potential Anal. 1 61-82. · Zbl 1081.31502 · doi:10.1007/BF00249786
[12]	Kesten, H. (1959a). Full Banach mean values on countable groups. Math. Scand. 7 146-156. · Zbl 0092.26704
[13]	Kesten, H. (1959b). Symmetric random walks on groups. Trans. Amer. Math. Soc. 92 336-354. · Zbl 0092.33503 · doi:10.2307/1993160
[14]	Li, W.-C. W. (2007). Ramanujan graphs and Ramanujan hypergraphs. In Automorphic Forms and Applications (P. Sarnak and F. Shahidi, eds.). IAS/Park City Math. Ser. 12 401-427. Amer. Math. Soc., Providence, RI. · Zbl 0677.31006
[15]	Lubotzky, A., Phillips, R. and Sarnak, P. (1988). Ramanujan graphs. Combinatorica 8 261-277. · Zbl 0661.05035 · doi:10.1007/BF02126799
[16]	Lyons, R. and Peres, Y. (2015). Probability on Trees and Networks . Preprint, Cambridge Univ. Press. Available at . · Zbl 1376.05002
[17]	Margulis, G. A. (1988). Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii 24 51-60.
[18]	Murty, M. R. (2003). Ramanujan graphs. J. Ramanujan Math. Soc. 18 33-52. · Zbl 1038.05038
[19]	Nilli, A. (1991). On the second eigenvalue of a graph. Discrete Math. 91 207-210. · Zbl 0771.05064 · doi:10.1016/0012-365X(91)90112-F
[20]	Northshield, S. (1992). Cogrowth of regular graphs. Proc. Amer. Math. Soc. 116 203-205. · Zbl 0756.60064 · doi:10.2307/2159315
[21]	Varopoulos, N. Th. (1985). Isoperimetric inequalities and Markov chains. J. Funct. Anal. 63 215-239. · Zbl 0573.60059 · doi:10.1016/0022-1236(85)90086-2