Connectivity properties of random subgraphs of the cube

The n ‐dimensional cube Q n is the graph whose vertices are the subsets of {1, n } where two such vertices are adjacent if and only if their symmetric difference is a singleton. Clearly Q n is an n‐connected graph of diameter and radius n. Write M = n2n −1 = e(Q n ) for the size of Q n . Let Q̃ = (Q t ) M 0 be a random Q̃ ‐process. Thus Q t is a spanning subgraph of Q n of size t , and Q t is obtained from Q t‐1 by the random addition of an edge of Q n not in Q t‐1 . Let t (k) = τ(Q̃ δ ≧ k) be the hitting time of the property of having minimal degree at least k. It is shown in [5] that, almost surely, at time t (1) the graph Q t becomes connected and that in fact the diameter of Q t at this point is n + 1. Here we generalize this result by showing that, for any fixed k≧2 , almost surely at time t (k) the graph Q t acquires the extremely strong property that any two of its vertices are connected by k internally vertex‐disjoint paths each of length at most n , except for possibly one, which may have length n + 1. In particular, the hitting time of k ‐connectedness is almost surely t (k) . © 1995 John Wiley & Sons, Inc.