{
  "id": "1003.3515",
  "version": "v1",
  "published": "2010-03-18T06:30:59.000Z",
  "updated": "2010-03-18T06:30:59.000Z",
  "title": "Explicit expanders with cutoff phenomena",
  "authors": [
    "Eyal Lubetzky",
    "Allan Sly"
  ],
  "comment": "17 pages, 2 figures",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "The cutoff phenomenon describes a sharp transition in the convergence of an ergodic finite Markov chain to equilibrium. Of particular interest is understanding this convergence for the simple random walk on a bounded-degree expander graph. The first example of a family of bounded-degree graphs where the random walk exhibits cutoff in total-variation was provided only very recently, when the authors showed this for a typical random regular graph. However, no example was known for an explicit (deterministic) family of expanders with this phenomenon. Here we construct a family of cubic expanders where the random walk from a worst case initial position exhibits total-variation cutoff. Variants of this construction give cubic expanders without cutoff, as well as cubic graphs with cutoff at any prescribed time-point.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-03-18T06:30:59.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60B10",
      "60J10",
      "60G50",
      "05C81"
    ],
    "keywords": [
      "cutoff phenomenon",
      "explicit expanders",
      "ergodic finite markov chain",
      "cubic expanders",
      "worst case initial position"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1003.3515L"
    }
  }
}