THE EVOLUTION OF RANDOM SUBGRAPHS OF THE CUBE

Let (Q(t))0M be a random Q(n)-process, that is let Q0 be the empty spanning subgraph of the cube Q(n) and, for 1 less-than-or-equal-to t less-than-or-equal-to M = nN/2 = n2n-1, let the graph Q(t) be obtained from Q(t-1) by the random addition of an edge of Q(n) not present in Q(t-1). When t is about N/2, a typical Q(t) undergoes a certain "phase transition": the component structure changes in a sudden and surprising way. Let t = (1 + epsilon)N/2 where epsilon is independent of n. Then all the components of a typical Q(t) have o(N) vertices if epsilon < 0, while if epsilon > 0 then, as proved by Ajtai, Komlos, and Szemeredi, a typical Q(t) has a "giant" component with at least alpha(epsilon)N vertices, where alpha(epsilon) > 0. In this note we give essentially best possible results concerning the emergence of this giant component close to the time of phase transition. Our results imply that if eta > 0 is fixed and t less-than-or-equal-to (1 - n-eta)N/2, then all components of a typical Q(t) have at most n(beta(eta)) vertices, where beta(eta) > 0. More importantly, if 60(log n)3/n less-than-or-equal-to epsilon = epsilon(n) = o(1), then the largest component of a typical Q(t) has about 2-epsilon-N vertices, while the second largest component has order O(n-epsilon(-2)). Loosely put, the evolution of a typical Q(n) process is such that shortly after time N/2 the appearance of each new edge results in the giant component acquiring 4 new vertices.