CONNECTIVITY AND DYNAMICS FOR RANDOM SUBGRAPHS OF THE DIRECTED CUBE

Let alpha is an element of R, epsilon = (alpha + o(1))/n and p = 1/2(1 + epsilon). Denote by ($) over right arrow Q(p)(n) a random subgraph of the directed n-dimensional hypercube ($) over right arrow Q(n), whe re each of the n2(n) directed edges is chosen independently with proba bility p. Then the probability that ($) over right arrow Q(p)(n) is st rong-connected tends to exp{-2 exp{-alpha}}. The proof of this main re sult uses a double-randomization technique. Similar techniques may be employed to yield a simpler proof of the known analogous result for un directed random graphs on the cube. The main result is applied to the analysis of the dynamic behavior of asynchronous binary networks. It i mplies that for almost all random binary networks with fixpoints, conv ergence to a fixpoint is guaranteed.