{
  "id": "1610.01765",
  "version": "v1",
  "published": "2016-10-06T07:54:39.000Z",
  "updated": "2016-10-06T07:54:39.000Z",
  "title": "The uniform model for $d$-regular graphs: concentration inequalities for linear forms and the spectral gap",
  "authors": [
    "Konstantin Tikhomirov",
    "Pierre Youssef"
  ],
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "In this paper, we address the problem of estimating the spectral gap of random $d$-regular graphs distributed according to the uniform model. Namely, let $\\alpha>0$ be any positive number and let integers $d$ and $n$ satisfy $n^\\alpha\\leq d\\leq n/2$. Let $G$ be uniformly distributed on the set of all $d$-regular simple undirected graphs on $n$ vertices, and let $\\lambda(G)$ be the second largest (in absolute value) eigenvalue of $G$. We show that $\\lambda(G)\\leq C_\\alpha \\sqrt{d}$ with probability at least $1-\\frac{1}{n}$, where $C_\\alpha>0$ may depend only on $\\alpha$. Combined with earlier results in this direction covering the case of sparse random graphs, this completely settles the problem of estimating the magnitude of $\\lambda(G)$ up to a multiplicative constant for all values of $n$ and $d$. The result is obtained as a consequence of an estimate for the second largest singular value of adjacency matrices of random {\\it directed} graphs with predefined degree sequences. As the main technical tool, we prove a concentration inequality for arbitrary linear forms on the space of matrices, where the probability measure is induced by the adjacency matrix of a random directed graph with prescribed degree sequences. The proof is a non-trivial application of the Freedman inequality for martingales, combined with boots-trapping and tensorization arguments. Our method bears considerable differences compared to the approach used by Broder, Frieze, Suen and Upfal (1999) who established the upper bound for $\\lambda(G)$ for $d=o(\\sqrt{n})$, and to the argument of Cook, Goldstein and Johnson (2015) who derived a concentration inequality for linear forms and estimated $\\lambda(G)$ in the range $d= O(n^{2/3})$ using size-biased couplings.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-10-06T07:54:39.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "concentration inequality",
      "spectral gap",
      "uniform model",
      "regular graphs",
      "adjacency matrix"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}