THE MEASURABLE KESTEN THEOREM

• 成果类型: Article
• 署名作者: Abert, Miklos; Glasner, Yair; Virag, Balint
• 署名单位: HUN-REN; HUN-REN Alfred Renyi Institute of Mathematics; Ben-Gurion University of the Negev; University of Toronto; University of Toronto
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/14-AOP937
• 发表日期: 2016
• 页码: 1601-1646
• 关键词: ramanujan graphs; EIGENVALUE

摘要

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 vertical bar G vertical bar. 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.