{
  "id": "1910.10121",
  "version": "v1",
  "published": "2019-10-22T17:12:25.000Z",
  "updated": "2019-10-22T17:12:25.000Z",
  "title": "Edge rigidity and universality of random regular graphs of intermediate degree",
  "authors": [
    "Roland Bauerschmidt",
    "Jiaoyang Huang",
    "Antti Knowles",
    "Horng-Tzer Yau"
  ],
  "categories": [
    "math.PR"
  ],
  "abstract": "For random $d$-regular graphs on $N$ vertices with $1 \\ll d \\ll N^{2/3}$, we develop a $d^{-1/2}$ expansion of the local eigenvalue distribution about the Kesten-McKay law up to order $d^{-3}$. This result is valid up to the edge of the spectrum. It implies that the eigenvalues of such random regular graphs are more rigid than those of Erd\\H{o}s-R\\'enyi graphs of the same average degree. As a first application, for $1 \\ll d \\ll N^{2/3}$, we show that all nontrivial eigenvalues of the adjacency matrix are with very high probability bounded in absolute value by $(2 + o(1)) \\sqrt{d - 1}$. As a second application, for $N^{2/9} \\ll d \\ll N^{1/3}$, we prove that the extremal eigenvalues are concentrated at scale $N^{-2/3}$ and their fluctuations are governed by Tracy-Widom statistics. Thus, in the same regime of $d$, $52\\%$ of all $d$-regular graphs have second-largest eigenvalue strictly less than $2 \\sqrt{d - 1}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-10-22T17:12:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60B20",
      "15B52",
      "05C80"
    ],
    "keywords": [
      "random regular graphs",
      "edge rigidity",
      "intermediate degree",
      "universality",
      "local eigenvalue distribution"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}