×

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)

Keywords:

topology
PDFBibTeX XMLCite