{
  "id": "1012.4097",
  "version": "v3",
  "published": "2010-12-18T15:08:11.000Z",
  "updated": "2011-11-07T13:46:04.000Z",
  "title": "The spectrum of random lifts",
  "authors": [
    "Louigi Addario-Berry",
    "Simon Griffiths"
  ],
  "comment": "35 pages; substantially revised, constants in the main results improved",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "For a fixed d-regular graph H, a random n-lift is obtained by replacing each vertex v of H by a \"fibre\" containing n vertices, then placing a uniformly random matching between fibres corresponding to adjacent vertices of H. We show that with extremely high probability, all eigenvalues of the lift that are not eigenvalues of H, have order O(sqrt(d)). In particular, if H is Ramanujan then its n-lift is with high probability nearly Ramanujan. We also show that any exceptionally large eigenvalues of the n-lift that are not eigenvalues of H, are overwhelmingly likely to have been caused by a dense subgraph of size O(|E(H)|).",
  "revisions": [
    {
      "version": "v3",
      "updated": "2011-11-07T13:46:04.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C50",
      "06C05"
    ],
    "keywords": [
      "random lifts",
      "adjacent vertices",
      "fixed d-regular graph",
      "random n-lift",
      "dense subgraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 35,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1012.4097A"
    }
  }
}