{
  "id": "2412.20263",
  "version": "v1",
  "published": "2024-12-28T20:34:12.000Z",
  "updated": "2024-12-28T20:34:12.000Z",
  "title": "Ramanujan Property and Edge Universality of Random Regular Graphs",
  "authors": [
    "Jiaoyang Huang",
    "Theo Mckenzie",
    "Horng-Tzer Yau"
  ],
  "comment": "153 pages, 3 figures",
  "categories": [
    "math.PR",
    "math-ph",
    "math.CO",
    "math.MP",
    "math.SP"
  ],
  "abstract": "We consider the normalized adjacency matrix of a random $d$-regular graph on $N$ vertices with any fixed degree $d\\geq 3$ and denote its eigenvalues as $\\lambda_1=d/\\sqrt{d-1}\\geq \\lambda_2\\geq\\lambda_3\\cdots\\geq \\lambda_N$. We establish the following two results as $N\\rightarrow \\infty$. (i) With high probability, all eigenvalues are optimally rigid, up to an additional $N^{{\\rm o}(1)}$ factor. Specifically, the fluctuations of bulk eigenvalues are bounded by $N^{-1+{\\rm o}(1)}$, and the fluctuations of edge eigenvalues are bounded by $N^{-2/3+{\\rm o}(1)}$. (ii) Edge universality holds for random $d$-regular graphs. That is, the distributions of $\\lambda_2$ and $-\\lambda_N$ converge to the Tracy-Widom$_1$ distribution associated with the Gaussian Orthogonal Ensemble. As a consequence, for sufficiently large $N$, approximately $69\\%$ of $d$-regular graphs on $N$ vertices are Ramanujan, meaning $\\max\\{\\lambda_2,|\\lambda_N|\\}\\leq 2$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-12-28T20:34:12.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60B20",
      "05C80",
      "05C48",
      "60F05"
    ],
    "keywords": [
      "random regular graphs",
      "ramanujan property",
      "edge universality holds",
      "fluctuations",
      "normalized adjacency matrix"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 153,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}