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 (1)

• Random subgraphs of finite graphs: III. The phase transition for the $n$-cube

Cited by in corpus (3)

• Expansion in $n^{-1}$ for percolation critical values on the $n$-cube and $Z^n$: the first three terms
• Asymptotic expansions in $n^{-1}$ for percolation critical values on the $n$-cube and ${\mathbb{Z}}^n$
• Random subgraphs of finite graphs: II. The lace expansion and the triangle condition