{
  "id": "1502.04482",
  "version": "v1",
  "published": "2015-02-16T10:12:45.000Z",
  "updated": "2015-02-16T10:12:45.000Z",
  "title": "A new proof of Friedman's second eigenvalue Theorem and its extension to random lifts",
  "authors": [
    "Charles Bordenave"
  ],
  "comment": "39 pages",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "It was conjectured by Alon and proved by Friedman that a random $d$-regular graph has nearly the largest possible spectral gap, more precisely, the largest absolute value of the non-trivial eigenvalues of its adjacency matrix is at most $2\\sqrt{d-1} +o(1)$ with probability tending to one as the size of the graph tends to infinity. We give a new proof of this statement. We also study related questions on random $n$-lifts of graphs and improve a recent result by Friedman and Kohler.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-02-16T10:12:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C50"
    ],
    "keywords": [
      "friedmans second eigenvalue theorem",
      "random lifts",
      "largest absolute value",
      "spectral gap",
      "regular graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 39,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}