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

Christian Borgs, Jennifer T. Chayes, Remco van der Hofstad, Gordon Slade, Joel Spencer

Published 2004-01-08Version 1

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.