Random subgraphs of finite graphs: I. The scaling window under the triangle condition

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|=Θ(\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 $ε=\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 $Θ(\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$.

References in corpus (2)

• On the Number of Incipient Spanning Clusters
• Random subgraphs of finite graphs: III. The phase transition for the $n$-cube

Cited by in corpus (35)

• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
• Critical random graphs: Diameter and mixing time
• Percolation on dense graph sequences
• Uniqueness and non-uniqueness in percolation theory
• Giant vacant component left by a random walk in a random d-regular graph
• Random graph asymptotics on high-dimensional tori. II. Volume, diameter and mixing time
• Universal Finite-Size Scaling for Percolation Theory in High Dimensions
• Clique percolation
• The scaling window of the 5D Ising model with free boundary conditions
• On the critical probability in percolation
• On the derivation of mean-field percolation critical exponents from the triangle condition
• Weakly self-avoiding walk on a high-dimensional torus
• The phase transition in bounded-size Achlioptas processes
• The critical random graph, with martingales
• Expansion of percolation critical points for Hamming graphs
• Random subgraphs of the 2D Hamming graph: the supercritical phase
• Expansion in $n^{-1}$ for percolation critical values on the $n$-cube and $Z^n$: the first three terms
• Critical Percolation on Random Networks with Prescribed Degrees
• Unlacing the lace expansion: a survey to hypercube percolation
• Cycle structure of percolation on high-dimensional tori
• On Coloring Random Subgraphs of a Fixed Graph
• Asymptotic expansions in $n^{-1}$ for percolation critical values on the $n$-cube and ${\mathbb{Z}}^n$
• Mean-field conditions for percolation on finite graphs
• Random graph asymptotics on high-dimensional tori
• Slightly subcritical hypercube percolation
• Scaling limits for the threshold window: When does a monotone Boolean function flip its outcome?
• Emergence of a Giant Component in Random Site Subgraphs of a d-Dimensional Hamming Torus
• Susceptibility of random graphs with given vertex degrees
• A note about critical percolation on finite graphs
• Convergence of mixing times for sequences of random walks on finite graphs
• Connectivity Threshold for random subgraphs of the Hamming graph
• Critical percolation on random regular graphs
• A branching process with deletions and mergers that matches the threshold for hypercube percolation
• Perspectives in Statistical Mechanics
• Random subgraphs of finite graphs: II. The lace expansion and the triangle condition