## Abstract

Let α ∈R, ε=(α+o(1)))/n and p=1/2(1+ε). Denote by {Mathematical expression} a random subgraph of the directed n-dimensional hypercube {Mathematical expression}, where each of the n2^{ n} directed edges is chosen independently with probability p. Then the probability that {Mathematical expression} is strong-connected tends to exp{-2exp{-α}}. The proof of this main result uses a double-randomization technique. Similar techniques may be employed to yield a simpler proof of the known analogous result for undirected random graphs on the cube. The main result is applied to the analysis of the dynamic behavior of asynchronous binary networks. It implies that for almost all random binary networks with fixpoints, convergence to a fixpoint is guaranteed.

Original language | English (US) |
---|---|

Pages (from-to) | 321-328 |

Number of pages | 8 |

Journal | Israel Journal of Mathematics |

Volume | 83 |

Issue number | 3 |

DOIs | |

State | Published - Oct 1 1993 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)