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

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 size of the component containing 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 component inside a scaling window given by vertical bar epsilon vertical bar=Theta(2(n/3)) is of size Theta(2(2n/3)), below this scaling window it is at most 2(log 2)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) >= e(-en1/3) the size of the largest component is at least Theta(epsilon 2(n)), 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.