Zentralblatt MATH

Publications of (and about) Paul Erdös
Zbl.No:  103.16301
Autor:  Erdös, Pál; Rényi, Alfréd
Title:  On the evolution of random graphs (In English)
Source:  Publ. Math. Inst. Hung. Acad. Sci., Ser. A 5, 17-61 (1960).
Review:  A random graph \Gamman,N is a undirected finite graph without parallel edges and slings. \Gamman,N has n points P1,...,Pn and N edges (Pi,Pj), which are chosen at random so that all \binom{\binom{n}{2}}{N} = Cn,N possible choices are supposed to be equiprobable. Let be Pn,N (A) = An,N/Cn,N the probability that \Gamman,N has the property A, where An,N denotes the number of graphs with the given points P1,...,Pn, with N edges (Pi, Pj) and with the property A. \Gamman,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 +oo for n ––> +oo such that limn ––> +oo Pn,N(n) (A) = 0 or = 1 if limn ––> +oo {N(n) \over A(n)} = 0 or = +oo. A(n) is a "regular threshold function" of A if there exists a probability distribution function F(x) such that limn ––> +oo Pn,N(n)(A) = F(x) if limn ––> +oo {N(n) \over A(n)} = x, where 0 < x <+oo 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) ~ cn, where c > 0. Let \gammak denote the number of cycles of order k contained in \Gamman,N (k = 3,4,...). Then we have limn ––> +oo Pn,N(n) (\gammak = j) = \lambdaj 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.Culik
Classif.:  * 05C80 Random graphs
Index Words:  topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page