Empirical Spectral Distributions of Sparse Random Graphs

Amir Dembo, Eyal Lubetzky, Yumeng Zhang

Research output: Chapter in Book/Report/Conference proceedingChapter

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
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