On the almost eigenvectors of random regular graphs. (English) Zbl 1414.05259

Summary: Let \(d \geq 3\) be fixed and \(G\) be a large random \(d\)-regular graph on \(n\) vertices. We show that if \(n\) is large enough then the entry distribution of every almost eigenvector of \(G\) (with entry sum 0 and normalized to have length \(\sqrt{n}\)) is close to some Gaussian distribution \(N(0,\sigma)\) in the weak topology where \(0\leq\sigma\leq 1\). Our theorem holds even in the stronger sense when many entries are looked at simultaneously in small random neighborhoods of the graph. Furthermore, we also get the Gaussianity of the joint distribution of several almost eigenvectors if the corresponding eigenvalues are close. Our proof uses graph limits and information theory. Our results have consequences for factor of i.i.d. processes on the infinite regular tree.
In particular, we obtain that if an invariant eigenvector process on the infinite \(d\)-regular tree is in the weak closure of factor of i.i.d. processes then it has Gaussian distribution.


05C80 Random graphs (graph-theoretic aspects)
60B20 Random matrices (probabilistic aspects)
15B52 Random matrices (algebraic aspects)
Full Text: DOI arXiv Euclid


[1] 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
[2] Anantharaman, N. and Le Masson, E. (2015). Quantum ergodicity on large regular graphs. Duke Math. J.164 723–765. · Zbl 1386.58015
[3] Anantharaman, N. and Sabri, M. (2017). Quantum ergodicity on graphs: From spectral to spatial delocalization. Preprint. Available at arXiv:1704.02766 [math.SP]. · Zbl 1376.82091
[4] Backhausz, Á. and Szegedy, B. (2018). On large girth regular graphs and random processes on trees. Random Structures Algorithms. To appear. · Zbl 1401.05267
[5] Backhausz, Á., Szegedy, B. and Virág, B. (2015). Ramanujan graphings and correlation decay in local algorithms. Random Structures Algorithms47 424–435. · Zbl 1325.05159
[6] Backhausz, Á. and Virág, B. (2017). Spectral measures of factor of i.i.d. processes on vertex-transitive graphs. Ann. Inst. Henri Poincaré Probab. Stat.53 2260–2278. · Zbl 1387.60063
[7] Bauerschmidt, R., Huang, J., Knowles, A. and Yau, H.-T. (2016). Local Kesten–McKay law for random regular graphs. Preprint. Available at arXiv:1609.09052 [math.PR].
[8] Bauerschmidt, R., Huang, J., Knowles, A. and Yau, H.-T. (2017). Bulk eigenvalue statistics for random regular graphs. Ann. Probab.45 3626–3663. · Zbl 1379.05098
[9] Bauerschmidt, R., Knowles, A. and Yau, H.-T. (2017). Local semicircle law for random regular graphs. Comm. Pure Appl. Math.70 1898–1960. · Zbl 1372.05194
[10] Benaych-Georges, F., Knowles, A. and Yau, H.-T. (2017). Lectures on the local semicircle law for Wigner matrices. In Advanced Topics in Random Matrices. Panoramas et Synthèses53. Société Mathématique de France, Paris. · Zbl 1403.60012
[11] Bloemendal, A., Knowles, A., Yau, H.-T. and Yin, J. (2016). On the principal components of sample covariance matrices. Probab. Theory Related Fields164 459–552. · Zbl 1339.15023
[12] Bollobás, B. (2001). Random Graphs, 2nd ed. Cambridge Studies in Advanced Mathematics73. Cambridge Univ. Press, Cambridge.
[13] Bollobás, B. and Riordan, O. (2011). Sparse graphs: Metrics and random models. Random Structures Algorithms39 1–38.
[14] Bordenave, C. (2015). A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts. Preprint. Available at arXiv:1502.04482 [math.CO].
[15] Bourgade, P., Huang, J. and Yau, H.-T. (2017). Eigenvector statistics of sparse random matrices. Electron. J. Probab.22 Paper No. 64, 38. · Zbl 1372.05195
[16] Bourgade, P. and Yau, H.-T. (2017). The eigenvector moment flow and local quantum unique ergodicity. Comm. Math. Phys.350 231–278. · Zbl 1379.58014
[17] Bowen, L. (2010). The ergodic theory of free group actions: Entropy and the \(f\)-invariant. Groups Geom. Dyn.4 419–432. · Zbl 1201.37006
[18] Brooks, S. and Lindenstrauss, E. (2013). Non-localization of eigenfunctions on large regular graphs. Israel J. Math.193 1–14. · Zbl 1317.05110
[19] Conley, C. T., Marks, A. S. and Tucker-Drob, R. D. (2016). Brooks’ theorem for measurable colorings. Forum Math. Sigma4 e16, 23. · Zbl 06601294
[20] Cover, T. M. and Thomas, J. A. (2006). Elements of Information Theory, 2nd ed. Wiley-Interscience, Hoboken, NJ. · Zbl 1140.94001
[21] Csóka, E., Gerencsér, B., Harangi, V. and Virág, B. (2015). Invariant Gaussian processes and independent sets on regular graphs of large girth. Random Structures Algorithms47 284–303.
[22] Dumitriu, I., Johnson, T., Pal, S. and Paquette, E. (2013). Functional limit theorems for random regular graphs. Probab. Theory Related Fields156 921–975. · Zbl 1271.05088
[23] Dumitriu, I. and Pal, S. (2012). Sparse regular random graphs: Spectral density and eigenvectors. Ann. Probab.40 2197–2235. · Zbl 1255.05173
[24] Elon, Y. (2009). Gaussian waves on the regular tree. Preprint. Available at arXiv:0907.5065 [math-ph].
[25] Friedman, J. (2008). A proof of Alon’s second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc.195 viii \(+\) 100. · Zbl 1177.05070
[26] Friedman, N. A. and Ornstein, D. S. (1970). On isomorphism of weak Bernoulli transformations. Adv. Math.5 365–394. · Zbl 0203.05801
[27] Gaboriau, D. and Lyons, R. (2009). A measurable-group-theoretic solution to von Neumann’s problem. Invent. Math.177 533–540. · Zbl 1182.43002
[28] Gamarnik, D. and Sudan, M. (2014). Limits of local algorithms over sparse random graphs [extended abstract]. In ITCS’14—Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science 369–375. ACM, New York. · Zbl 1365.05277
[29] Geisinger, L. (2015). Convergence of the density of states and delocalization of eigenvectors on random regular graphs. J. Spectr. Theory5 783–827. · Zbl 1384.60024
[30] Harangi, V. and Virág, B. (2015). Independence ratio and random eigenvectors in transitive graphs. Ann. Probab.43 2810–2840. · Zbl 1323.05101
[31] Hatami, H., Lovász, L. and Szegedy, B. (2014). Limits of locally-globally convergent graph sequences. Geom. Funct. Anal.24 269–296. · Zbl 1294.05109
[32] Huang, J., Landon, B. and Yau, H.-T. (2015). Bulk universality of sparse random matrices. J. Math. Phys.56 123301, 19. · Zbl 1329.05262
[33] Knowles, A. and Yin, J. (2013). Eigenvector distribution of Wigner matrices. Probab. Theory Related Fields155 543–582. · Zbl 1268.15033
[34] Lubotzky, A., Phillips, R. and Sarnak, P. (1988). Ramanujan graphs. Combinatorica8 261–277. · Zbl 0661.05035
[35] Lyons, R. (2017). Factors of IID on trees. Combin. Probab. Comput.26 285–300. · Zbl 1371.05129
[36] Lyons, R. and Nazarov, F. (2011). Perfect matchings as IID factors on non-amenable groups. European J. Combin.32 1115–1125. · Zbl 1229.05115
[37] O’Rourke, S., Vu, V. and Wang, K. (2016). Eigenvectors of random matrices: A survey. J. Combin. Theory Ser. A144 361–442. · Zbl 1347.15044
[38] Puder, D. (2015). Expansion of random graphs: New proofs, new results. Invent. Math.201 845–908. · Zbl 1320.05115
[39] Rahman, M. (2016). Factor of IID percolation on trees. SIAM J. Discrete Math.30 2217–2242. · Zbl 1351.05206
[40] Rahman, M. and Virág, B. (2017). Local algorithms for independent sets are half-optimal. Ann. Probab.45 1543–1577. · Zbl 1377.60049
[41] Tao, T. and Vu, V. (2012). Random matrices: Universal properties of eigenvectors. Random Matrices Theory Appl.1 1150001, 27. · Zbl 1248.15031
[42] Wormald, N. C. (1999). Models of random regular graphs. In Surveys in Combinatorics, 1999 (Canterbury). London Mathematical Society Lecture Note Series267 239–298. Cambridge Univ. Press, Cambridge. · 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. 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.