×

On the spectral distribution of large weighted random regular graphs. (English) Zbl 1305.15079

Summary: McKay proved the limiting spectral measures of the ensembles of \(d\)-regular graphs with \(N\) vertices converge to Kesten’s measure as \(N \to \infty\). Given a large \(d\)-regular graph we assign random weights, drawn from some distribution \(\mathcal{W}\), to its edges. We study the relationship between \(\mathcal{W}\) and the associated limiting spectral distribution obtained by averaging over the weighted graphs. We establish the existence of a unique “eigendistribution” (a weight distribution \(\mathcal{W}\) such that the associated limiting spectral distribution is a rescaling of \(\mathcal{W}\)). Initial investigations suggested that the eigendistribution was the semi-circle distribution, which by Wigner’s Law is the limiting spectral measure for real symmetric matrices. We prove this is not the case, though the deviation between the eigendistribution and the semi-circular density is small (the first seven moments agree, and the difference in each higher moment is \(O(1/d^{2}))\). Our analysis uses combinatorial results about closed acyclic walks in large trees, which may be of independent interest.

MSC:

15B52 Random matrices (algebraic aspects)
05C80 Random graphs (graph-theoretic aspects)
60F05 Central limit and other weak theorems
05C22 Signed and weighted graphs
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] DOI: 10.1007/BF02579166 · Zbl 0661.05053 · doi:10.1007/BF02579166
[2] Anderson G. W., Cambridge Studies in Advanced Mathematics 118, in: An Introduction to Random Matrices (2010)
[3] Bai Z., Statist. Sinica 9 pp 611– (1999)
[4] Bien F., Notices Amer. Math. Soc. 36 pp 5– (1989)
[5] Billingsley P., Probability and Measure (1995)
[6] DOI: 10.1016/j.laa.2003.08.015 · Zbl 1042.15014 · doi:10.1016/j.laa.2003.08.015
[7] DOI: 10.1016/j.disc.2007.08.023 · Zbl 1153.05062 · doi:10.1016/j.disc.2007.08.023
[8] Bose A., J. Indian Statist. Assoc. 41 pp 221– (2003)
[9] DOI: 10.1142/S2010326314500075 · Zbl 1306.15032 · doi:10.1142/S2010326314500075
[10] DOI: 10.1214/009117905000000495 · Zbl 1094.15009 · doi:10.1214/009117905000000495
[11] DOI: 10.1017/CBO9780511615825 · doi:10.1017/CBO9780511615825
[12] DOI: 10.1214/11-AOP673 · Zbl 1255.05173 · doi:10.1214/11-AOP673
[13] Erdos L., Comm. Pure Appl. Math. 63 pp 895– (2010)
[14] Erdos L., Int. Math. Res. Not. 2010 pp 436– (2010)
[15] DOI: 10.3390/sym1010064 · doi:10.3390/sym1010064
[16] DOI: 10.1515/9781400835416 · doi:10.1515/9781400835416
[17] DOI: 10.1215/S0012-7094-93-06921-9 · Zbl 0785.05066 · doi:10.1215/S0012-7094-93-06921-9
[18] Friedman J., Mem. Amer. Math. Soc. 195 pp viii+100– (2008)
[19] DOI: 10.1088/1367-2630/11/7/073005 · doi:10.1088/1367-2630/11/7/073005
[20] DOI: 10.1007/s10959-005-3518-5 · Zbl 1086.15024 · doi:10.1007/s10959-005-3518-5
[21] DOI: 10.1007/978-1-4612-1544-8_12 · doi:10.1007/978-1-4612-1544-8_12
[22] DOI: 10.1063/1.1667610 · Zbl 1068.05062 · doi:10.1063/1.1667610
[23] DOI: 10.1007/s10959-011-0391-2 · Zbl 1298.60016 · doi:10.1007/s10959-011-0391-2
[24] DOI: 10.1007/BF02126799 · Zbl 0661.05035 · doi:10.1007/BF02126799
[25] McDiarmid C., Electron. J. Combin. 19 pp #P53– (2012)
[26] McDiarmid C., Electron. J. Combin. 20 pp #P52– (2013)
[27] DOI: 10.1016/0024-3795(81)90150-6 · Zbl 0468.05039 · doi:10.1016/0024-3795(81)90150-6
[28] Mehta M., Random Matrices (1991)
[29] DOI: 10.1080/10586458.2008.10129029 · Zbl 1151.05043 · doi:10.1080/10586458.2008.10129029
[30] DOI: 10.1137/0206022 · Zbl 0361.05035 · doi:10.1137/0206022
[31] DOI: 10.1017/CBO9780511895593 · doi:10.1017/CBO9780511895593
[32] Sarnak P., Notices Amer. Math. Soc. 51 pp 762– (2004)
[33] DOI: 10.1109/18.556667 · Zbl 0943.94543 · doi:10.1109/18.556667
[34] DOI: 10.1007/s10955-011-0243-6 · Zbl 1225.82032 · doi:10.1007/s10955-011-0243-6
[35] DOI: 10.2307/2324428 · Zbl 0747.60019 · doi:10.2307/2324428
[36] DOI: 10.1090/S0273-0979-09-01252-X · Zbl 1168.15018 · doi:10.1090/S0273-0979-09-01252-X
[37] DOI: 10.1007/s00220-010-1044-5 · Zbl 1202.15038 · doi:10.1007/s00220-010-1044-5
[38] DOI: 10.1002/rsa.20406 · Zbl 1257.05089 · doi:10.1002/rsa.20406
[39] Vengerovsky V., Zh. Mat. Fiz. Anal. Geom. 10 pp 240– (2014) · Zbl 1298.05211 · doi:10.15407/mag10.02.240
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.