# zbMATH — the first resource for mathematics

On the evolution of random graphs. (English) Zbl 0103.16301
A random graph $$\Gamma_{n,N}$$ is a undirected finite graph without parallel edges and slings. $$\Gamma_{n,N}$$ has $$n$$ points $$P_1,...,P_n$$ and $$N$$ edges ($$P_i,P_j)$$, which are chosen at random so that all $$\binom{\binom{n}{2}}{N} = C_{n,N}$$ possible choices are supposed to be equiprobable. Let be $$P_{n,N} (A)=A_{n,N}/C_{n,N}$$ the probability that $$\Gamma_{n,N}$$ has the property $$A$$, where $$A_{n,N}$$ denotes the number of graphs with the given points $$P_1,...,P_n$$, with $$N$$ edges $$(P_i, P_j)$$ and with the property $$A$$. $$\Gamma_{n,N}$$ is studied under the condition that $$N$$ is increased, i.e. if $$N$$ is equal, or asymptotically equal, to a given function $$N(n)$$ of $$n$$. For many properties $$A$$ there is shown that there exists a ”threshold function” $$A(n)$$ of the property $$A$$ tendig monotonically to $$+ \infty$$ for $$n \to +\infty$$ such that $$\lim_{n \to +\infty} P_{n,N(n)} (A)=0$$ or =1 if $$\lim_{n \to +\infty} {N(n) \over A(n)}=0$$ or $$=+\infty$$. $$A(n)$$ is a ”regular threshold function” of $$A$$ if there exists a probability distribution function $$F(x)$$ such that $$\lim_{n \to +\infty} P_{n,N(n)}(A) = F(x)$$ if $$\lim_{n \to +\infty} {N(n) \over A(n)} =x$$, where $$0 < x < +\infty$$ and $$x$$ is a point of continuity of $$F(x)$$. The investigated properties are as follows: the presence of certain subgraphs (e. g. trees, complete subgraphs, cycles, etc.) or connectedness, number of components etc. The results are of the following type: Theorem 3a. Suppose that $$N(n) \sim cn$$, where $$c > 0$$. Let $$\gamma_k$$ denote the number of cycles of order $$k$$ contained in $$\Gamma_{n,N}$$ $$(k=3,4,...)$$. Then we have $$\lim_{n \to +\infty} P_{n,N(n)} (\gamma_k = j) = \lambda^j e^{-\lambda}/j!$$, where $$j=0,1,...$$ and $$\lambda= (2c)^k/2k$$. Thus the threshold distribution corresponding to the threshold function $$A(n)=n$$ for the property that the graph contains a cycle of order $$k$$ is $$1-e^{-(2c)^k/2k}$$.
Reviewer: K.Čulik

##### MSC:
 05C80 Random graphs (graph-theoretic aspects)
topology