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

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

2004-01-08

arxiv.org/abs/math/0401071v1

Mathematics

Probability

14 pages

Scientific paper

We study random subgraphs of the $n$-cube $\{0,1\}^n$, where nearest-neighbor edges are occupied with probability $p$. Let $p_c(n)$ be the value of $p$ for which the expected cluster size of a fixed vertex attains the value $\lambda 2^{n/3}$, where $\lambda$ is a small positive constant. Let $\epsilon=n(p-p_c(n))$. In two previous papers, we showed that the largest cluster inside a scaling window given by $|\epsilon|=\Theta(2^{-n/3})$ is of size $\Theta(2^{2n/3})$, below this scaling window it is at most $2(\log2) n\epsilon^{-2}$, and above this scaling window it is at most $O(\epsilon 2^n)$. In this paper, we prove that for $p - p_c(n) \geq e^{-cn^{1/3}}$ the size of the largest cluster is at least $\Theta(\epsilon 2^n)$, which is of the same order as the upper bound. This provides an understanding of the phase transition that goes far beyond that obtained by previous authors. The proof is based on a method that has come to be known as ``sprinkling,'' and relies heavily on the specific geometry of the $n$-cube.

Affiliated with

Also associated with

No associations

Rating

Random subgraphs of finite graphs: III. The phase transition for the $n$-cube 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: III. The phase transition for the $n$-cube, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random subgraphs of finite graphs: III. The phase transition for the $n$-cube will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-62933