Local Kesten-McKay law for random regular graphs. (English) Zbl 1414.05260
Summary: We study the adjacency matrices of random \(d\)-regular graphs with large but fixed degree \(d\). In the bulk of the spectrum \({[-2\sqrt{d-1}+\varepsilon, 2\sqrt{d-1}-\varepsilon]}\) down to the optimal spectral scale, we prove that the Green’s functions can be approximated by those of certain infinite tree-like (few cycles) graphs that depend only on the local structure of the original graphs. This result implies that the Kesten-McKay law holds for the spectral density down to the smallest scale and the complete delocalization of bulk eigenvectors. Our method is based on estimating the Green’s function of the adjacency matrices and a resampling of the boundary edges of large balls in the graphs.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
References:
| [1] | Adlam, B., Che, Z.: Spectral statistics of sparse random graphs with a general degree distribution (2015). Preprint arXiv:1509.03368 |
| [2] | Aizenman M., Sims R., Warzel S.: Absolutely continuous spectra of quantum tree graphs with weak disorder. Commun. Math. Phys. 264(2), 371-389 (2006) · Zbl 1233.34009 |
| [3] | Aizenman, M., Sims, R., Warzel, S.: Fluctuation based proof of the stability of ac spectra of random operators on tree graphs. In: Recent Advances in Differential Equations and Mathematical Physics, volume 412 of Contemporary Mathematics, pp. 1-14. American Mathematical Society, Providence (2006) · Zbl 1111.82022 |
| [4] | Aizenman M., Sims R., Warzel S.: Stability of the absolutely continuous spectrum of random Schrödinger operators on tree graphs. Probab. Theory Relat. Fields 136(3), 363-394 (2006) · Zbl 1169.82007 |
| [5] | Aizenman, M., Warzel, S.: Persistence under weak disorder of AC spectra of quasi-periodic Schrödinger operators on trees graphs. Mosc. Math. J. 5(3), 499-506, 742 (2005) · Zbl 1124.47027 |
| [6] | Aizenman, M., Warzel, S.: The canopy graph and level statistics for random operators on trees. Math. Phys. Anal. Geom. 9(4), 291-333 (2007), 2006 · Zbl 1138.47032 |
| [7] | Aizenman, M., Warzel, S.: Disorder-induced delocalization on tree graphs. In: Mathematical Results in Quantum Physics, pp. 107-109. World Scientific, Hackensack (2011) |
| [8] | Aizenman, M., Warzel, S.: Absolutely continuous spectrum implies ballistic transport for quantum particles in a random potential on tree graphs. J. Math. Phys. 53(9), 095205, 15 (2012) · Zbl 1278.81090 |
| [9] | Aizenman M., Warzel S.: Resonant delocalization for random Schrödinger operators on tree graphs. J. Eur. Math. Soc. (JEMS) 15(4), 1167-1222 (2013) · Zbl 1267.47064 |
| [10] | Aizenman M., Warzel S.: On the ubiquity of the Cauchy distribution in spectral problems. Probab. Theory Relat. Fields 163(1-2), 61-87 (2015) · Zbl 1330.60042 |
| [11] | Aizenman, M., Warzel, S.: Random Operators: Disorder Effects on Quantum Spectra and Dynamics, volume 168 of Graduate Studies in Mathematics. American Mathematical Society, Providence (2015) · Zbl 1333.82001 |
| [12] | Ajanki, O.H., Erdős, L., Krüger, T.: Universality for general wigner-type matrices. In: Probability Theory and Related Fields, pp. 1-61 (2016) · Zbl 1403.60010 |
| [13] | Alon, N.: Eigenvalues and expanders. Combinatorica 6(2), 83-96, (1986). Theory of computing (Singer Island, Fla., 1984) · Zbl 0661.05053 |
| [14] | Anantharaman, N.: Quantum ergodicity on regular graphs. Comm. Math. Phys. 353(2), 633-690 (2017) · Zbl 1368.58015 |
| [15] | Anantharaman N., Le Masson E.: Quantum ergodicity on large regular graphs. Duke Math. J. 164(4), 723-765 (2015) · Zbl 1386.58015 |
| [16] | Backhausz, A., Szegedy, B.: On the almost eigenvectors of random regular graphs (2016). Preprint arXiv:1607.04785 · Zbl 1401.05267 |
| [17] | Bass H.: The Ihara-Selberg zeta function of a tree lattice. Int. J. Math. 3(6), 717-797 (1992) · Zbl 0767.11025 |
| [18] | Bauerschmidt, R., Huang, J., Knowles, A., Yau, H.-T.: Bulk eigenvalue statistics for random regular graphs. Ann. Probab. (2016+) (to appear) · Zbl 1379.05098 |
| [19] | Bauerschmidt, R., Knowles, A., Yau, H.-T.: Local semicircle law for random regular graphs. Commun. Pure Appl. Math. (2016+) (to appear) · Zbl 1372.05194 |
| [20] | Bordenave, C.: A new proof of Friedman’s second eigenvalue Theorem and its extension to random lifts (2015). Preprint arXiv:1502.04482 · Zbl 1462.05324 |
| [21] | Bourgade P., Erdős L., Yau H.-T., Yin J.: Fixed energy universality for generalized Wigner matrices. Commun. Pure Appl. Math. 69(10), 1815-1881 (2016) · Zbl 1354.15025 |
| [22] | Bourgade, P., Huang, J., Yau, H.-T.: Eigenvector statistics of sparse random matrices. Electron. J. Probab. 22(64), 38 (2017) · Zbl 1372.05195 |
| [23] | Bourgade, P., Yau, H.-T.: The eigenvector moment flow and local quantum unique ergodicity. Commun. Math. Phys. 350(1), 231-278 (2017) · Zbl 1379.58014 |
| [24] | Brooks S., Lindenstrauss E.: Non-localization of eigenfunctions on large regular graphs. Isr. J. Math. 193(1), 1-14 (2013) · Zbl 1317.05110 |
| [25] | Brooks, S., Masson, E.L., Lindenstrauss, E.: Quantum ergodicity and averaging operators on the sphere (2015) · Zbl 1404.35307 |
| [26] | Combes J.M., Thomas L.: Asymptotic behaviour of eigenfunctions for multiparticle Schrödinger operators. Commun. Math. Phys. 34, 251-270 (1973) · Zbl 0271.35062 |
| [27] | Cook, N.: On the singularity of adjacency matrices for random regular digraphs. Probab. Theory Relat. Fields 167(1-2), 143-200 (2017) · Zbl 1365.05260 |
| [28] | Cook, N.A.: The circular law for random regular digraphs with random edge weights. Random Matrices Theory Appl. 6(3), 1750012 (2017) · Zbl 1370.05078 |
| [29] | Cook, N.A., Goldstein, L., Johnson, T.: Size biased couplings and the spectral gap for random regular graphs. Ann. Probab. 46(1), 72-125 (2018) · Zbl 1386.05105 |
| [30] | De Luca A., Altshuler B.L., Kravtsov V.E., Scardicchio A.: Anderson localization on the bethe lattice: nonergodicity of extended states. Phys. Rev. Lett. 113, 046806 (2014) |
| [31] | Dumitriu I., Johnson T., Pal S., Paquette E.: Functional limit theorems for random regular graphs. Probab. Theory Relat. Fields 156(3-4), 921-975 (2013) · Zbl 1271.05088 |
| [32] | Dumitriu I., Pal S.: Sparse regular random graphs: spectral density and eigenvectors. Ann. Probab. 40(5), 2197-2235 (2012) · Zbl 1255.05173 |
| [33] | Elon, Y.: Gaussian waves on the regular tree (2009). Preprint arXiv:0907.5065 |
| [34] | Erdős L., Knowles A., Yau H.-T., Yin J.: Spectral statistics of Erdős-Rényi Graphs II: eigenvalue spacing and the extreme eigenvalues. Commun. Math. Phys. 314(3), 587-640 (2012) · Zbl 1251.05162 |
| [35] | Erdős L., Knowles A., Yau H.-T., Yin J.: Spectral statistics of Erdős-Rényi graphs I: local semicircle law. Ann. Probab. 41(3B), 2279-2375 (2013) · Zbl 1272.05111 |
| [36] | Erdős L., Péché S., Ramírez J.A., Schlein B., Yau H.-T.: Bulk universality for Wigner matrices. Commun. Pure Appl. Math. 63(7), 895-925 (2010) · Zbl 1216.15025 |
| [37] | Erdős L., Ramírez J.A., Schlein B., Yau H.-T.: Universality of sine-kernel for Wigner matrices with a small Gaussian perturbation. Electron. J. Probab. 15(18), 526-603 (2010) · Zbl 1225.15034 |
| [38] | Erdős L., Schlein B., Yau H.-T.: Universality of random matrices and local relaxation flow. Invent. Math. 185(1), 75-119 (2011) · Zbl 1225.15033 |
| [39] | Erdős, L., Yau, H.-T.: A dynamical approach to random matrix theory. In: Courant Lecture Notes in Mathematics, Courant Institute of Mathematical Sciences, vol. 28. American Mathematical Society, New York, Providence, RI (2017) · Zbl 1379.15003 |
| [40] | Erdős L., Yau H.-T.: Gap universality of generalized Wigner and \[{\beta}\] β-ensembles. J. Eur. Math. Soc. (JEMS) 17(8), 1927-2036 (2015) · Zbl 1333.15031 |
| [41] | Erdős L., Yau H.-T., Yin J.: Bulk universality for generalized Wigner matrices. Probab. Theory Relat. Fields 154(1-2), 341-407 (2012) · Zbl 1277.15026 |
| [42] | Friedman J.: A proof of Alon’s second eigenvalue conjecture and related problems. Mem. Am. Math. Soc. 195(910), viii+100 (2008) · Zbl 1177.05070 |
| [43] | Friedman, J., Kahn, J., Szemerédi, E.: On the second eigenvalue of random regular graphs. In: Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, STOC ’89, New York, NY, USA, pp. 587-598 (1989). ACM |
| [44] | Geisinger L.: Convergence of the density of states and delocalization of eigenvectors on random regular graphs. J. Spectr. Theory 5(4), 783-827 (2015) · Zbl 1384.60024 |
| [45] | Geisinger L.: Poisson eigenvalue statistics for random Schrödinger operators on regular graphs. Ann. Henri Poincaré 16(8), 1779-1806 (2015) · Zbl 1321.81025 |
| [46] | Horton, M.D., Newland, D.B., Terras, A.A.: The contest between the kernels in the Selberg trace formula for the (q + 1)-regular tree. In: The Ubiquitous Heat Kernel, volume 398 of Contemporary Mathematics, pp. 265-293. American Mathematical Society, Providence (2006) · Zbl 1147.11031 |
| [47] | Huang, J., Landon, B.: Spectral statistics of sparse Erdős-Rényi graph Laplacians (2015). Preprint arXiv:1510.06390 · Zbl 1434.60030 |
| [48] | Huang, J., Landon, B., Yau, H.-T.: Bulk universality of sparse random matrices. J. Math. Phys. 56(12), 123301 (2015) · Zbl 1329.05262 |
| [49] | Ihara Y.: On discrete subgroups of the two by two projective linear group over \[{{\mathfrak{p}}}\] p-adic fields. J. Math. Soc. Japan 18, 219-235 (1966) · Zbl 0158.27702 |
| [50] | Jakobson, D., Miller, S.D., Rivin, I., Rudnick, Z.: Eigenvalue spacings for regular graphs. In: Emerging Applications of Number Theory (Minneapolis, MN, 1996), volume 109 of IMA Volumes in Mathematics and its Applications, pp. 317-327. Springer, New York (1999) · Zbl 1071.81522 |
| [51] | Johansson K.: Universality of the local spacing distribution in certain ensembles of Hermitian Wigner matrices. Commun. Math. Phys. 215(3), 683-705 (2001) · Zbl 0978.15020 |
| [52] | Johnson, T.: Exchangeable pairs, switchings, and random regular graphs. Electron. J. Combin. 22(1):Paper 1.33, 28 (2015) · Zbl 1307.05205 |
| [53] | Kesten H.: Symmetric random walks on groups. Trans. Am. Math. Soc. 92, 336-354 (1959) · Zbl 0092.33503 |
| [54] | Klein A.: Extended states in the Anderson model on the Bethe lattice. Adv. Math. 133(1), 163-184 (1998) · Zbl 0899.60088 |
| [55] | Knowles A., Yin J.: Eigenvector distribution of Wigner matrices. Probab. Theory Relat. Fields 155(3-4), 543-582 (2013) · Zbl 1268.15033 |
| [56] | Landon, B., Yau, H.-T.: Convergence of local statistics of Dyson Brownian motion. Comm. Math. Phys. 355(3), 949-1000 (2017) · Zbl 1378.60106 |
| [57] | Le Masson E.: Pseudo-differential calculus on homogeneous trees. Ann. Henri Poincaré 15(9), 1697-1732 (2014) · Zbl 1328.35344 |
| [58] | Lubetzky E., Sly A.: Cutoff phenomena for random walks on random regular graphs. Duke Math. J. 153(3), 475-510 (2010) · Zbl 1202.60012 |
| [59] | Lubotzky A., Phillips R., Sarnak P.: Ramanujan graphs. Combinatorica 8(3), 261-277 (1988) · Zbl 0661.05035 |
| [60] | Luca, A.D., Scardicchio, A., Kravtsov, V.E., Altshuler, B.L.: Support set of random wave-functions on the Bethe lattice (2013). Preprint arXiv:1401.0019 |
| [61] | Marcus A.W., Spielman D.A., Srivastava N.: Interlacing families I: bipartite Ramanujan graphs of all degrees. Ann. Math. (2) 182(1), 307-325 (2015) · Zbl 1316.05066 |
| [62] | Margulis G.A.: Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii 24(1), 51-60 (1988) · Zbl 0708.05030 |
| [63] | McKay B.D.: The expected eigenvalue distribution of a large regular graph. Linear Algebra Appl. 40, 203-216 (1981) · Zbl 0468.05039 |
| [64] | McKay B.D.: Asymptotics for symmetric 0-1 matrices with prescribed row sums. Ars Combin. 19(A), 15-25 (1985) · Zbl 0568.05032 |
| [65] | McKay, B.D., Wormald, N.C., Wysocka, B.: Short cycles in random regular graphs. Electron. J. Combin. 11(1): 66 (2004) · Zbl 1063.05122 |
| [66] | Metz F.L., Parisi G., Leuzzi L.: Finite-size corrections to the spectrum of regular random graphs: An analytical solution. Phys. Rev. E 90, 052109 (2014) |
| [67] | Miller S.J., Novikoff T.: The distribution of the largest nontrivial eigenvalues in families of random regular graphs. Exp. Math. 17(2), 231-244 (2008) · Zbl 1151.05043 |
| [68] | Oren, I., Smilansky, U.: Trace formulas and spectral statistics for discrete Laplacians on regular graphs (II). J. Phys. A 43(22), 225205, 13 (2010) · Zbl 1190.81052 |
| [69] | O’Rourke, S., Vu, V., Wang, K.: Eigenvectors of random matrices: a survey. J. Combin. Theory Ser. A 144, 361-442 (2016) · Zbl 1347.15044 |
| [70] | Puder D.: Expansion of random graphs: new proofs, new results. Invent. Math. 201(3), 845-908 (2015) · Zbl 1320.05115 |
| [71] | Sarnak, P.: What is an expander? Notices Am. Math. Soc. 51(7), 762-763 (2004) · Zbl 1161.05341 |
| [72] | Smilansky, U.: Discrete graphs—a paradigm model for quantum chaos. In: Chaos, volume 66 of Progress in Mathematical Physics, pp. 97-124. Birkhäuser/Springer, Basel (2013) · Zbl 1319.81047 |
| [73] | Spencer, T.: Duality, statistical mechanics, and random matrices. In: Current Developments in Mathematics 2012, pp. 229-260. International Press, Somerville (2013) · Zbl 1292.82006 |
| [74] | Tao T., Vu V.: Random matrices: universality of local eigenvalue statistics. Acta Math. 206(1), 127-204 (2011) · Zbl 1217.15043 |
| [75] | Tao, T., Vu, V.: Random matrices: universal properties of eigenvectors. Random Matrices Theory Appl. 1(1):1150001, 27 (2012) · Zbl 1248.15031 |
| [76] | Terras, A.: Zeta Functions of Graphs: A Stroll Through the Garden, volume 128 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (2011) · Zbl 1206.05003 |
| [77] | Terras, A., Wallace, D.: Selberg’s trace formula on the k-regular tree and applications. Int. J. Math. Math. Sci. 8:501-526 (2003) · Zbl 1083.11032 |
| [78] | Tran L.V., Vu V.H., Wang K.: Sparse random graphs: eigenvalues and eigenvectors. Random Struct. Algorithms 42(1), 110-134 (2013) · Zbl 1257.05089 |
| [79] | Vu, V.: Random discrete matrices. In: Horizons of Combinatorics, volume 17 of Bolyai Society Mathematical Studies, pp. 257-280. Springer, Berlin (2008) · Zbl 1154.15024 |
| [80] | Wormald, N.C.: Models of random regular graphs. In: Surveys in Combinatorics, 1999 (Canterbury), volume 267 of London Mathematical Society Lecture Note Series, pp. 239-298. Cambridge University Press, Cambridge (1999) · Zbl 0935.05080 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
