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

Abstract

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
PublisherBirkhauser
Pages319-345
Number of pages27
DOIs
StatePublished - 2021

Publication series

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

Keywords

  • Empirical spectral distribution
  • Random graphs
  • Random matrices

ASJC Scopus subject areas

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

Fingerprint

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

Cite this