Empirical Spectral Distributions of Sparse Random Graphs

Amir Dembo, Eyal Lubetzky, Yumeng Zhang

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review


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.

Original languageEnglish (US)
Title of host publicationProgress in Probability
Subtitle of host publicationIn and Out of Equilibrium 3, Celebrating Vladas Sidoravicius
Number of pages27
StatePublished - 2021

Publication series

NameProgress in Probability
ISSN (Print)1050-6977
ISSN (Electronic)2297-0428


  • Empirical spectral distribution
  • Random graphs
  • Random matrices

ASJC Scopus subject areas

  • Statistics and Probability
  • Applied Mathematics
  • Mathematical Physics
  • Mathematics (miscellaneous)


Dive into the research topics of 'Empirical Spectral Distributions of Sparse Random Graphs'. Together they form a unique fingerprint.

Cite this