TY - CHAP

T1 - Empirical Spectral Distributions of Sparse Random Graphs

AU - Dembo, Amir

AU - Lubetzky, Eyal

AU - Zhang, Yumeng

N1 - Funding Information:
Acknowledgments The authors wish to thank Nick Cook, Alice Guionnet, Allan Sly and Ofer Zeitouni for many helpful discussions. A.D. was supported in part by NSF grant DMS-1613091. E.L. was supported in part by NSF grants DMS-1513403 and DMS-1812095.
Publisher Copyright:
© 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - We study the spectrum of a random multigraph with a degree sequence Dn=(Di)i=1n and average degree 1 ≪ ωn ≪ n, generated by the configuration model, and also the spectrum of the analogous random simple graph. We show that, when the empirical spectral distribution (ESD) of ωn−1Dn converges weakly to a limit ν, under mild moment assumptions (e.g., Di∕ωn are i.i.d. with a finite second moment), the ESD of the normalized adjacency matrix converges in probability to ν⊠ σSC, the free multiplicative convolution of ν with the semicircle law. Relating this limit with a variant of the Marchenko–Pastur law yields the continuity of its density (away from zero), and an effective procedure for determining its support. Our proof of convergence is based on a coupling between the random simple graph and multigraph with the same degrees, which might be of independent interest. We further construct and rely on a coupling of the multigraph to an inhomogeneous Erdős-Rényi graph with the target ESD, using three intermediate random graphs, with a negligible fraction of edges modified in each step.

AB - We study the spectrum of a random multigraph with a degree sequence Dn=(Di)i=1n and average degree 1 ≪ ωn ≪ n, generated by the configuration model, and also the spectrum of the analogous random simple graph. We show that, when the empirical spectral distribution (ESD) of ωn−1Dn converges weakly to a limit ν, under mild moment assumptions (e.g., Di∕ωn are i.i.d. with a finite second moment), the ESD of the normalized adjacency matrix converges in probability to ν⊠ σSC, the free multiplicative convolution of ν with the semicircle law. Relating this limit with a variant of the Marchenko–Pastur law yields the continuity of its density (away from zero), and an effective procedure for determining its support. Our proof of convergence is based on a coupling between the random simple graph and multigraph with the same degrees, which might be of independent interest. We further construct and rely on a coupling of the multigraph to an inhomogeneous Erdős-Rényi graph with the target ESD, using three intermediate random graphs, with a negligible fraction of edges modified in each step.

KW - Empirical spectral distribution

KW - Random graphs

KW - Random matrices

UR - http://www.scopus.com/inward/record.url?scp=85115902325&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115902325&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-60754-8_15

DO - 10.1007/978-3-030-60754-8_15

M3 - Chapter

AN - SCOPUS:85115902325

T3 - Progress in Probability

SP - 319

EP - 345

BT - Progress in Probability

PB - Birkhauser

ER -