{
  "id": "1803.11553",
  "version": "v2",
  "published": "2018-03-30T17:51:40.000Z",
  "updated": "2020-01-08T18:15:26.000Z",
  "title": "Asymptotics in percolation on high-girth expanders",
  "authors": [
    "Michael Krivelevich",
    "Eyal Lubetzky",
    "Benny Sudakov"
  ],
  "comment": "22 pages, 1 figure",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We consider supercritical bond percolation on a family of high-girth $d$-regular expanders. Alon, Benjamini and Stacey (2004) established that its critical probability for the appearance of a linear-sized (\"giant'') component is $p_c=1/(d-1)$. Our main result recovers the sharp asymptotics of the size and degree distribution of the vertices in the giant and its 2-core at any $p>p_c$. It was further shown in [ABS04] that the second largest component, at any $0<p<1$, has size at most $n^{\\omega}$ for some $\\omega<1$. We show that, unlike the situation in the classical Erd\\H{o}s-R\\'enyi random graph, the second largest component in bond percolation on a regular expander, even with an arbitrarily large girth, can have size $n^{\\omega'}$ for $\\omega'$ arbitrarily close to $1$. Moreover, as a by-product of that construction, we answer negatively a question of Benjamini (2013) on the relation between the diameter of a component in percolation on expanders and the existence of a giant component. Finally, we establish other typical features of the giant component, e.g., the existence of a linear path.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2020-01-08T18:15:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60K35",
      "05C80"
    ],
    "keywords": [
      "high-girth expanders",
      "second largest component",
      "giant component",
      "regular expander",
      "linear path"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}