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

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

2004-01-08

arxiv.org/abs/math/0401069v1

Mathematics

Probability

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Random subgraphs of finite graphs: I. The scaling window under the triangle condition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Random subgraphs of finite graphs: I. The scaling window under the triangle condition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random subgraphs of finite graphs: I. The scaling window under the triangle condition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-62913