{
  "id": "math/0610459",
  "version": "v2",
  "published": "2006-10-15T21:01:33.000Z",
  "updated": "2016-07-31T13:37:30.000Z",
  "title": "The mixing time of the giant component of a random graph",
  "authors": [
    "Itai Benjamini",
    "Gady Kozma",
    "Nicholas Wormald"
  ],
  "comment": "21 pages. New version fixes a small mistake in the proof of Theorem 2.3 discovered by Johannes Blank",
  "journal": "Random Structures Algorithms 45:3 (2014), 383-407",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We show that the total variation mixing time of the simple random walk on the giant component of supercritical Erdos-Renyi graphs is log^2 n. This statement was only recently proved, independently, by Fountoulakis and Reed. Our proof follows from a structure result for these graphs which is interesting in its own right. We show that these graphs are \"decorated expanders\" - an expander glued to graphs whose size has constant expectation and exponential tail, and such that each vertex in the expander is glued to no more than a constant number of decorations.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-10-15T21:01:33.000Z",
      "comment": "21 pages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2016-07-31T13:37:30.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60J10"
    ],
    "keywords": [
      "giant component",
      "random graph",
      "total variation mixing time",
      "simple random walk",
      "supercritical erdos-renyi graphs"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math.....10459B"
    }
  }
}