Abstract
Let Cn denote the graph with vertices (ε{lunate}1,...,ε{lunate}n), ε{lunate}i = 0, 1 and vertices adjacent if they differ in exactly one coordinate. We call Cn the n-cube. Let G = Gn,p denote the random subgraph of Cn defined by letting Prob({i,j} ∈ G) = p for all i, j ∈ Cn and letting these probabilities be mutually independent. We wish to understand the "evolution" of G as a function of p. Section 1 consists of speculations, without proofs, involving this evolution. Set f{hook}n = Prof(Gn,p is connected) We show in Section 2: Theorem Lim n f{hook}n(p) = 0 if p<0.5e-1 if p=0.51 if p>0.5. The first and last parts were shown by Yu. Burtin[1]. For completeness, we show all three parts.
Original language | English (US) |
---|---|
Pages (from-to) | 33-39 |
Number of pages | 7 |
Journal | Computers and Mathematics with Applications |
Volume | 5 |
Issue number | 1 |
DOIs | |
State | Published - 1979 |
ASJC Scopus subject areas
- Modeling and Simulation
- Computational Theory and Mathematics
- Computational Mathematics