{
  "id": "0709.1719",
  "version": "v2",
  "published": "2007-09-11T20:40:42.000Z",
  "updated": "2008-11-25T03:00:56.000Z",
  "title": "Mean-field conditions for percolation on finite graphs",
  "authors": [
    "Asaf Nachmias"
  ],
  "comment": "29 pages. to appear in Geometric and Functional Analysis",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Let G_n be a sequence of finite transitive graphs with vertex degree d=d(n) and |G_n|=n. Denote by p^t(v,v) the return probability after t steps of the non-backtracking random walk on G_n. We show that if p^t(v,v) has quasi-random properties, then critical bond-percolation on G_n has a scaling window of width n^{-1/3}, as it would on a random graph. A consequence of our theorems is that if G_n is a transitive expander family with girth at least (2/3 + eps) \\log_{d-1} n, then the size of the largest component in p-bond-percolation with p={1 +O(n^{-1/3}) \\over d-1} is roughly n^{2/3}. In particular, bond-percolation on the celebrated Ramanujan graph constructed by Lubotzky, Phillips and Sarnak has the above scaling window. This provides the first examples of quasi-random graphs behaving like random graphs with respect to critical bond-percolation.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-11-25T03:00:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "finite graphs",
      "mean-field conditions",
      "scaling window",
      "critical bond-percolation",
      "largest component"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0709.1719N"
    }
  }
}