Random Subgraphs of Finite Graphs: III. The Phase Transition for the n-cube

We study random subgraphs of the n-cube f0; 1gn, where nearest-neighbor edges are occupied with probability p. Let pc(n) be the value of p for which the expected size of the component containing a fixed vertex attains the value ¸2n=3, where ¸ is a small positive constant. Let ² = n(p¡pc(n)). In two previous papers, we showed that the largest component inside a scaling window given by j²j = £(2¡n=3) is of size £(22n=3), below this scaling window it is at most 2(log 2)n²¡2, and above this scaling window it is at most O(²2n). In this paper, we prove that for p ¡ pc(n) ¸ e¡cn1=3 the size of the largest component is at least £(²2n), which is of the same order as the upper bound. 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.