Random graph asymptotics on high-dimensional tori. II. Volume, diameter and mixing time

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.

16 pages. v4 incorporates an erratum to be published in a forthcoming issue of Probab. Theory Relat. Fields

References in corpus (6)

• The Alexander-Orbach conjecture holds in high dimensions
• Critical random graphs: Diameter and mixing time
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Random subgraphs of the 2D Hamming graph: the supercritical phase
• Critical percolation on random regular graphs
• Mean-field conditions for percolation on finite graphs

Cited by in corpus (15)

• Non-vanishing boundary effects and quasi-first order phase transitions in high dimensional Ising models
• Finite size scaling of the 5D Ising model with free boundary conditions
• Critical percolation clusters in seven dimensions and on a complete graph
• Universal Finite-Size Scaling for Percolation Theory in High Dimensions
• Mixing time of near-critical random graphs
• The scaling window of the 5D Ising model with free boundary conditions
• Weakly self-avoiding walk on a high-dimensional torus
• Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
• Complete graph asymptotics for the Ising and random cluster models on 5D grids with cyclic boundary
• On breadth-first constructions of scaling limits of random graphs and random unicellular maps
• Unlacing the lace expansion: a survey to hypercube percolation
• Cycle structure of percolation on high-dimensional tori
• Scaling limits for the threshold window: When does a monotone Boolean function flip its outcome?
• Scaling limits and universality: Critical percolation on weighted graphs converging to an $L^3$ graphon
• Convergence of mixing times for sequences of random walks on finite graphs