Connectivity and dynamics for random subgraphs of the directed cube

Béla Bollobás, Craig Gotsman, Eli Shamir

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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 languageEnglish (US)
Pages (from-to)321-328
Number of pages8
JournalIsrael Journal of Mathematics
Issue number3
StatePublished - Oct 1 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'Connectivity and dynamics for random subgraphs of the directed cube'. Together they form a unique fingerprint.

Cite this