{
  "id": "1811.07554",
  "version": "v2",
  "published": "2018-11-19T08:36:42.000Z",
  "updated": "2020-11-28T05:39:06.000Z",
  "title": "Upper Tails for Edge Eigenvalues of Random Graphs",
  "authors": [
    "Bhaswar B. Bhattacharya",
    "Shirshendu Ganguly"
  ],
  "comment": "15 pages",
  "journal": "SIAM Journal on Discrete Mathematics, Vol. 34 (2), 1069-1083, 2020",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "The upper tail problem for the largest eigenvalue of the Erd\\H{o}s--R\\'enyi random graph $\\mathcal{G}_{n,p}$ is to estimate the probability that the largest eigenvalue of the adjacency matrix of $\\mathcal{G}_{n,p}$ exceeds its typical value by a factor of $1+\\delta$. In this note we show that for $\\delta >0$ fixed, and $p \\rightarrow 0$ such that $n^{\\frac{1}{2}} p \\rightarrow \\infty$, the upper tail probability for the largest eigenvalue of $\\mathcal{G}_{n,p}$ is $$\\exp\\left[-(1+o(1)) \\min\\left\\{\\tfrac{(1+\\delta)^2}{2}, \\delta(1+\\delta) \\right\\} n^{2}p^{2}\\log (1/p)\\right].$$ In the same regime of $p$, we show that the second largest eigenvalue $\\lambda_2( \\mathcal G_{n,p})$ of the adjacency matrix of $\\mathcal{G}_{n,p}$ satisfies $$\\mathbb P(\\lambda_2(\\mathcal G_{n,p})\\ge \\delta np) = \\exp\\left[-(1+o(1)) \\tfrac{1}{2} \\delta^2n^2p^2 \\log (1/p) \\right],$$ where $\\delta =\\delta_n < 1$ can depend on $n$ such that $\\delta n^{\\frac{1}{2}} p \\rightarrow \\infty$, which covers deviations of $\\lambda_2(\\mathcal G_{n,p})$ between $n^{\\frac{1}{2}}$ and $np$. Our arguments build on recent results on the large deviations of the largest eigenvalue and related non-linear functions of the adjacency matrix in terms of natural mean-field entropic variational problems.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2020-11-28T05:39:06.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graph",
      "edge eigenvalues",
      "adjacency matrix",
      "natural mean-field entropic variational problems",
      "second largest eigenvalue"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}