{
  "id": "0903.4279",
  "version": "v4",
  "published": "2009-03-25T12:13:05.000Z",
  "updated": "2019-07-15T15:06:21.000Z",
  "title": "Random graph asymptotics on high-dimensional tori. II. Volume, diameter and mixing time",
  "authors": [
    "Markus Heydenreich",
    "Remco van der Hofstad"
  ],
  "comment": "16 pages. v4 incorporates an erratum to be published in a forthcoming issue of Probab. Theory Relat. Fields",
  "journal": "Probab. Theory Relat. Fields 149(3-4): 397 - 415 (2011)",
  "doi": "10.1007/s00440-009-0258-y",
  "categories": [
    "math.PR",
    "math-ph",
    "math.MP"
  ],
  "abstract": "For critical bond-percolation on high-dimensional torus, this paper proves sharp lower bounds on the size of the largest cluster, removing a logarithmic correction in the lower bound in Heydenreich and van der Hofstad (2007). This improvement finally settles a conjecture by Aizenman (1997) about the role of boundary conditions in critical high-dimensional percolation, and it is a key step in deriving further properties of critical percolation on the torus. Indeed, a criterion of Nachmias and Peres (2008) implies appropriate bounds on diameter and mixing time of the largest clusters. We further prove that the volume bounds apply also to any finite number of the largest clusters. The main conclusion of the paper is that the behavior of critical percolation on the high-dimensional torus is the same as for critical Erdos-Renyi random graphs. In this updated version we incorporate an erratum to be published in a forthcoming issue of Probab. Theory Relat. Fields. This results in a modification of Theorem 1.2 as well as Proposition 3.1.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2009-11-20T15:06:09.000Z",
      "abstract": "For critical bond-percolation on high-dimensional torus, this paper proves sharp lower bounds on the size of the largest cluster, removing a logarithmic correction in the lower bound in Heydenreich and van der Hofstad (2007). This improvement finally settles a conjecture by Aizenman (1997) about the role of boundary conditions in critical high-dimensional percolation, and it is a key step in deriving further properties of critical percolation on the torus. Indeed, a criterion of Nachmias and Peres (2008) implies appropriate bounds on diameter and mixing time of the largest clusters. We further prove that the volume bounds apply also to any finite number of the largest clusters. Finally, we show that any weak limit of the largest connected component is non-degenerate, which can be viewed as a significant sign of critical behavior. The main conclusion of the paper is that the behavior of critical percolation on the high-dimensional torus is the same as for critical Erdos-Renyi random graphs.",
      "comment": "16 pages. Version v3: Removed Section 1.3 and shortened the presentation in Sections 1.4 and 4. To appear in Probab. Theory Related Fields",
      "journal": null,
      "doi": null
    },
    {
      "version": "v4",
      "updated": "2019-07-15T15:06:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60K35",
      "82B43"
    ],
    "keywords": [
      "random graph asymptotics",
      "high-dimensional torus",
      "mixing time",
      "largest cluster",
      "percolation"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "Springer"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0903.4279H"
    }
  }
}