## 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