On the evolution of random graphs pdf

On the evolution of random graphs pdf ~ ON THE EVOLUTION OF RANDOM GRAPHS by P. ERDŐS and A. RÉNYI Dedicated to Professor P. Turán at his 50th birthday. Introduction Our aim is to study the probable structure of a random graph rn N which has n given labelled vertices P, P2, . . . , Pn and N edges; we suppose that these N edges are chosen at random among the l n 1 possible edges, 2 so that all ~ 2 = Cn,n possible choices are supposed to be equiprobable . Thus 1V if G,,,,, denotes any one of the C,,N graphs formed from n given labelled points and having N edges, the probability that the random graph -Pn,N is identical with G,,,N is 1 . If A is a property which a graph may or may not possess, Cn,N we denote by PnN (A) the probability that the random graph T.,N possesses the property A, i. e. we put Pn,N (A) = An ' N where An,N denotes the Cn N number of those Gn,N which have the property A . An other equivalent formulation is the following : Let us suppose that n labelled vertices P,, P2, . . ., Pn are given. Let us choose at random an edge among the l n I possible edges, so that all these edges are equiprobable. After 2 this let us choose an other edge among the remaining In - 1 edges, and continue this process so that if already k edges are fixed, any of the remaining (n) - k edges have equal probabilities to be chosen as the next one . We shall 2 study the "evolution" of such a random graph if Nis increased. In this investi- gation we endeavour to find what is the "typical" structure at a given stage of evolution (i. e. if N is equal, or asymptotically equal, to a given function N(n) of n). By a "typical" structure we mean such a structure the probability of which tends to 1 if n -* + - when N = N(n). If A is such a property that lim Pn,N,(n) (A) = 1, we shall say that „almost all" graphs Gn,N(n) n--- possess this property. Download On the evolution of random graphs pdf