{
  "id": "math/0401069",
  "version": "v1",
  "published": "2004-01-08T10:35:26.000Z",
  "updated": "2004-01-08T10:35:26.000Z",
  "title": "Random subgraphs of finite graphs: I. The scaling window under the triangle condition",
  "authors": [
    "Christian Borgs",
    "Jennifer T. Chayes",
    "Remco van der Hofstad",
    "Gordon Slade",
    "Joel Spencer"
  ],
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We study random subgraphs of an arbitrary finite connected transitive graph $\\mathbb G$ obtained by independently deleting edges with probability $1-p$. Let $V$ be the number of vertices in $\\mathbb G$, and let $\\Omega$ be their degree. We define the critical threshold $p_c=p_c(\\mathbb G,\\lambda)$ to be the value of $p$ for which the expected cluster size of a fixed vertex attains the value $\\lambda V^{1/3}$, where $\\lambda$ is fixed and positive. We show that for any such model, there is a phase transition at $p_c$ analogous to the phase transition for the random graph, provided that a quantity called the triangle diagram is sufficiently small at the threshold $p_c$. In particular, we show that the largest cluster inside a scaling window of size $|p-p_c|=\\Theta(\\cn^{-1}V^{-1/3})$ is of size $\\Theta(V^{2/3})$, while below this scaling window, it is much smaller, of order $O(\\epsilon^{-2}\\log(V\\epsilon^3))$, with $\\epsilon=\\cn(p_c-p)$. We also obtain an upper bound $O(\\cn(p-p_c)V)$ for the expected size of the largest cluster above the window. In addition, we define and analyze the percolation probability above the window and show that it is of order $\\Theta(\\cn(p-p_c))$. Among the models for which the triangle diagram is small enough to allow us to draw these conclusions are the random graph, the $n$-cube and certain Hamming cubes, as well as the spread-out $n$-dimensional torus for $n>6$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2004-01-08T10:35:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60K35",
      "82B43"
    ],
    "keywords": [
      "scaling window",
      "finite graphs",
      "triangle condition",
      "triangle diagram",
      "random graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math......1069B"
    }
  }
}