{
  "id": "0801.1607",
  "version": "v2",
  "published": "2008-01-10T14:20:25.000Z",
  "updated": "2008-12-15T16:10:58.000Z",
  "title": "Random subgraphs of the 2D Hamming graph: the supercritical phase",
  "authors": [
    "Remco van der Hofstad",
    "Malwina J. Luczak"
  ],
  "comment": "31 pages",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We study random subgraphs of the 2-dimensional Hamming graph H(2,n), which is the Cartesian product of two complete graphs on $n$ vertices. Let $p$ be the edge probability, and write $p=\\frac{1+\\vep}{2(n-1)}$ for some $\\vep\\in \\R$. In Borgs et al., Random subgraphs of finite graphs: I. The scaling window under the triangle condition, Rand. Struct. Alg. (2005), and in Borgs et al., Random subgraphs of finite graphs: II. The lace expansion and the triangle condition, Ann. Probab. (2005), the size of the largest connected component was estimated precisely for a large class of graphs including H(2,n) for $\\vep\\leq \\Lambda V^{-1/3}$, where $\\Lambda > 0$ is a constant and $V=n^2$ denotes the number of vertices in H(2,n). Until now, no matching lower bound on the size in the supercritical regime has been obtained. In this paper we prove that, when $\\vep\\gg (\\log{V})^{1/3} V^{-1/3}$, then the largest connected component has size close to $2\\vep V$ with high probability. We thus obtain a law of large numbers for the largest connected component size, and show that the corresponding values of $p$ are supercritical. Barring the factor $(\\log{\\chs{V}})^{1/3}$, this identifies the size of the largest connected component all the way down to the critical $p$ window.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-12-15T16:10:58.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80"
    ],
    "keywords": [
      "largest connected component",
      "2d hamming graph",
      "supercritical phase",
      "finite graphs",
      "triangle condition"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 31,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0801.1607V"
    }
  }
}