{
  "id": "1610.05186",
  "version": "v1",
  "published": "2016-10-17T16:09:22.000Z",
  "updated": "2016-10-17T16:09:22.000Z",
  "title": "Empirical spectral distributions of sparse random graphs",
  "authors": [
    "Amir Dembo",
    "Eyal Lubetzky"
  ],
  "comment": "17 pages, 3 figures",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We study the spectrum of a random multigraph with a degree sequence $\\mathbf{D}_n=(D_i)_{i=1}^n$ and average degree $1 \\ll \\omega_n \\ll n$, generated by the configuration model. We show that, when the empirical spectral distribution (ESD) of $\\omega_n^{-1} \\mathbf{D}_n $ converges weakly to a limit $\\nu$, under mild moment assumptions, e.g., $D_i/\\omega_n$ are i.i.d. with a finite second moment), the ESD of the normalized adjacency matrix converges in probability to $\\nu\\boxtimes \\sigma_{\\mathrm{sc}}$, the free multiplicative convolution of $\\nu$ 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 of the graph to an inhomogeneous Erd\\H{o}s-R\\'enyi graph with the target ESD, using three intermediate random graphs, with a negligible number of edges modified in each step.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-10-17T16:09:22.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "empirical spectral distribution",
      "sparse random graphs",
      "normalized adjacency matrix converges",
      "intermediate random graphs",
      "finite second moment"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}