Random subgraphs of finite graphs: I. The scaling window under the triangle condition
Random Structures and Algorithms, 27 (2):
137--184 (Sep 8, 2005)DOI: 10.1002/rsa.20051
Abstract
We study random subgraphs of an arbitrary finite connected transitive graph
\$G\$ obtained by independently deleting edges with probability \$1-p\$.
Let \$V\$ be the number of vertices in \$G\$, and let \$Ømega\$ be their
degree. We define the critical threshold \$p\_c=p\_c(G,łambda)\$ to be the
value of \$p\$ for which the expected cluster size of a fixed vertex attains the
value \$V^1/3\$, where \$łambda\$ 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|=\Theta(\cn^-1V^-1/3)\$ is of size \$\Theta(V^2/3)\$, while below
this scaling window, it is much smaller, of order
\$O(\epsilon^-2łog(V\epsilon^3))\$, with \$\epsilon=\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 \$\Theta(\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\$.