Abért, Miklós and Glasner, Yair and Virág, Bálint (2016) The measurable kesten theorem. Annals of Probability, 44 (3). pp. 1601-1646. ISSN 0091-1798
|
Text
1111.2080.pdf Download (641kB) | Preview |
Abstract
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. © Institute of Mathematical Statistics, 2016.
Item Type: | Article |
---|---|
Additional Information: | N1 Funding Details: 11-07263, NSF, National Science Foundation N1 Funding Details: 11-07367, NSF, National Science Foundation N1 Funding Details: DMS-11-07452, NSF, National Science Foundation |
Uncontrolled Keywords: | Unimodular random graphs; Spectral radius; RAMANUJAN GRAPHS; Mass transport principal; Girth; Eigenvalue |
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 03 Jan 2017 08:02 |
Last Modified: | 03 Jan 2017 08:02 |
URI: | http://real.mtak.hu/id/eprint/44165 |
Actions (login required)
Edit Item |