Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 399.05041
Autor: Erdös, Paul; Spencer, Joel
Title: Evolution of the n-cube. (In English)
Source: Comput. Math. Appl. 5, 33-39 (1979).
Review: Let Cn denote the graph with vertices (\epsilon1,...,\epsilonn), \epsiloni = 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} in G) = p for all i,j in 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 fn(p) = Prof(Gn,p is connected). We show in Section 2: Theorem
| limnfn(p) = | 0 if p < 0.5 |
| e-1 if p = 0.5 |
| 1 if p > 0.5.. |
The first and last part were shown by Yu.Burtin. For completeness, we show all three parts.
Classif.: * 05C99 Graph theory
05C40 Connectivity
60C05 Combinatorial probability
60D05 Geometric probability
Keywords: evolution of the n-cube
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag