×

The measurable Kesten theorem. (English) Zbl 1339.05365

Summary: We give an explicit bound on the spectral radius in terms of the densities of short cycles in finite \(d\)-regular graphs. It follows that the a finite \(d\)-regular Ramanujan graph \(G\) contains a negligible number of cycles of size less than \(c\log\log| G|\).
We prove that infinite \(d\)-regular Ramanujan unimodular random graphs are trees. Through Benjamini-Schramm convergence this leads to the following rigidity result. If most eigenvalues of a \(d\)-regular finite graph \(G\) fall in the Alon-Boppana region, then the eigenvalue distribution of \(G\) is close to the spectral measure of the \(d\)-regular tree. In particular, \(G\) contains few short cycles.
In contrast, we show that \(d\)-regular unimodular random graphs with maximal growth are not necessarily trees.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
05C38 Paths and cycles
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
60G50 Sums of independent random variables; random walks
82C41 Dynamics of random walks, random surfaces, lattice animals, etc. in time-dependent statistical mechanics
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] Abért, M., Glasner, Y. and Virág, B. (2014). Kesten’s theorem for invariant random subgroups. Duke Math. J. 163 465-488. · Zbl 1344.20061
[2] Aldous, D. and Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Probab. 12 1454-1508. · Zbl 1131.60003
[3] Aldous, D. and Steele, J. M. (2004). The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures. Encyclopaedia Math. Sci. 110 1-72. Springer, Berlin. · Zbl 1037.60008
[4] Antal, P. and Pisztora, A. (1996). On the chemical distance for supercritical Bernoulli percolation. Ann. Probab. 24 1036-1048. · Zbl 0871.60089
[5] Bartholdi, L. (1999). Counting paths in graphs. Enseign. Math. (2) 45 83-131. · Zbl 0961.05032
[6] Benjamini, I. and Schramm, O. (2001). Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 13 pp. (electronic). · Zbl 1010.82021
[7] Bougerol, P. and Jeulin, T. (1999). Brownian bridge on hyperbolic spaces and on homogeneous trees. Probab. Theory Related Fields 115 95-120. · Zbl 0947.58032
[8] Boyd, A. V. (1992). Bounds for the Catalan numbers. Fibonacci Quart. 30 136-138. · Zbl 0751.11012
[9] Friedman, J. (2003). A proof of Alon’s second eigenvalue conjecture. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing 720-724 (electronic). ACM, New York. · Zbl 1192.05087
[10] Glasner, Y. (2003). Ramanujan graphs with small girth. Combinatorica 23 487-502. · Zbl 1045.05051
[11] Grigorchuk, R., Kaimanovich, V. A. and Nagnibeda, T. (2012). Ergodic properties of boundary actions and the Nielsen-Schreier theory. Adv. Math. 230 1340-1380. · Zbl 1278.37034
[12] Kesten, H. (1959). Symmetric random walks on groups. Trans. Amer. Math. Soc. 92 336-354. · Zbl 0092.33503
[13] Levin, D. A., Peres, Y. and Wilmer, E. L. (2009). Markov Chains and Mixing Times . Amer. Math. Soc., Providence, RI. · Zbl 1160.60001
[14] Lubotzky, A. (1994). Discrete Groups , Expanding Graphs and Invariant Measures. Progress in Mathematics 125 . Birkhäuser, Basel. · Zbl 0826.22012
[15] Lubotzky, A., Phillips, R. and Sarnak, P. (1988). Ramanujan graphs. Combinatorica 8 261-277. · Zbl 0661.05035
[16] Lyons, R. and Peres, Y. (2015). Cycle density in infinite Ramanujan graphs. Ann. Probab. 43 3337-3358. · Zbl 1346.60061
[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] Massey, W. S. (1977). Algebraic Topology : An Introduction . Springer, New York. · Zbl 0361.55002
[19] McKay, B. D. (1981). The expected eigenvalue distribution of a large regular graph. Linear Algebra Appl. 40 203-216. · Zbl 0468.05039
[20] Morgenstern, M. (1994). Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\). J. Combin. Theory Ser. B 62 44-62. · Zbl 0814.68098
[21] Nilli, A. (1991). On the second eigenvalue of a graph. Discrete Math. 91 207-210. · Zbl 0771.05064
[22] Ortner, R. and Woess, W. (2007). Non-backtracking random walks and cogrowth of graphs. Canad. J. Math. 59 828-844. · Zbl 1123.05081
[23] Paschke, W. L. (1993). Lower bound for the norm of a vertex-transitive graph. Math. Z. 213 225-239. · Zbl 0798.05036
[24] Serre, J.-P. (1997). Répartition asymptotique des valeurs propres de l’opérateur de Hecke \(T_{p}\). J. Amer. Math. Soc. 10 75-102. · Zbl 0871.11032
[25] Woess, W. (2000). Random Walks on Infinite Graphs and Groups. Cambridge Tracts in Mathematics 138 . Cambridge Univ. Press, Cambridge. · Zbl 0951.60002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.