##
**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 C^{n} denote the graph with vertices (\epsilon_{1},...,\epsilon_{n}), \epsilon_{i} = 0,1 and vertices adjacent if they differ in exactly one coordinate. We call C^{n} the n-cube. Let G = G_{n,p} denote the random subgraph of C^{n} defined by letting Prob(**{**i,j**}** in G) = p for all i,j in C^{n} 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_{n}(p) = Prof(G_{n,p} is connected). We show in Section 2: Theorem

**lim**_{n}f_{n}(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