ON THE EVOLUTION OF RANDOM GRAPHS by P. ERDŐS ad A. RÉNYI Itroductio Dedicated to Professor P. Turá at his 50th birthday. Our aim is to study the probable structure of a radom graph r N which has give

Please download to get full document.

View again

of 45
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Government Documents

Publish on:

Views: 23 | Pages: 45

Extension: PDF | Download: 0

ON THE EVOLUTION OF RANDOM GRAPHS by P. ERDŐS ad A. RÉNYI Itroductio Dedicated to Professor P. Turá at his 50th birthday. Our aim is to study the probable structure of a radom graph r N which has give labelled vertices P, P,..., P ad N edges ; we suppose that these N edges are chose at radom amog the l 1 possible edges, so that all ~ = C, possible choices are supposed to be equiprobable. Thus 1V if G,,,,, deotes ay oe of the C,,N graphs formed from give labelled poits ad havig N edges, the probability that the radom graph -P,N is idetical with G,,,N is 1. If A is a property which a graph may or may ot possess, C,N we deote by P N (A) the probability that the radom graph T.,N possesses the property A, i. e. we put P,N (A) = A 'N where A,N deotes the C N umber of those G,N which have the property A. A other equivalet formulatio is the followig : Let us suppose that labelled vertices P,, P,..., P are give. Let us choose at radom a edge amog the l I possible edges, so that all these edges are equiprobable. After this let us choose a other edge amog the remaiig I - 1 edges, ad cotiue this process so that if already k edges are fixed, ay of the remaiig () k edges have equal probabilities to be chose as the ext oe. We shall - study the evolutio of such a radom graph if N is icreased. I this ivestigatio we edeavour to fid what is the typical structure at a give stage of evolutio (i. e. if N is equal, or asymptotically equal, to a give fuctio N() of ). By a typical structure we mea such a structure the probability of which teds to 1 if -* + - whe N = N(). If A is such a property that lim P,N,( ) ( A) = 1, we shall say that almost all graphs G,N() --- possess this property. 17 A Matematikai Kutató Itézet Közleméye! V. A/1-. 18 ERDŐS-RÉNYi The study of the evolutio of graphs leads to rather surprisig results. For a umber of fudametal structural properties A there exists a fuctio A() tedig mootoically to + - for -i- - such that (1) lim P,N() (A) _ -+- i if lim X(v) = 0 - A() if lim N () +co. - A() If such a fuctio A() exists we shall call it a threshold fuctio of the property A. I may cases besides (1) it is also true that there exists a probability distributio fuctio F(x) so that if 0 x + - ad x is a poit of cotiuity of F(x) the () (3) lim P,N()(A) -.- Clearly (3) implies that i lim ) = x. M - + m P,N()(A)- F(x) if - - A() If () holds we shall say that A() is a regular threshold fuctio for the property A ad call the fuctio F(x) the threshold distributio fuctio of the property A. For certai properties A there exist two fuctios A,() ad A () both tedig mootoically to +- for -- -+-, ad satisfyig lim Á() = 0, - - Al() such that if lim () - A, () _ A () if lim N() - Al() _ a A () (4) lim P,N()(A) _ if lim sup N() 1 -a+m A l () 1 if liro if +() ~' ro A,.() If (3) holds we call the pair (Al(), A ()) a pair of sharp threshold -fuctios of the property A. It follows from (4) that if (A j (), A ()) is a pair of sharp threshold fuctios for the property A the A, () is a (ordiary) threshold fuctio for the property A ad the threshold distributio fuctio figurig i () is the degeerated distributio fuctio jr t (x) _ 1 0 (1 for x 1 for x 1 ON THE EVOLUTION OF RANDOM GRAPHS 1 9 ad covergece i () takes place for every x 1. I some cases besides (3) it is also true that there exists a probability distributio fuctio G(y) defied for -- y -)- - such that if y is a poit of cotiuity of G(y) the (ő) lim P.N()(A) = G(y) - if lím NT() - A,() = y -- x A () if (ő) holds we shall say that we have a regular sharp threshold ad shall call G(y) the sharp-threshold distributio fuctio of the property A. Oe of our chief aims will be to determie the threshold respectively sharp threshold fuctios, ad the correspodig distributio fuctios for the most obvious structural properties, e. g. the presece i r N of subgraphs of a give type (trees, cycles of give order, complete subgraphs etc.) further for certai global properties of the graph (coectedess, total umber of coected compoets, etc. ). I a previous paper [7] we have cosidered a special problem of this type ; we have show that deotig by C the property that the graph is coected, the pair C,() - 1 log. C () = is a pair of strog threshold fuctios for the property C, ad the correspodig sharp-threshold distributio fuctio is e -v ; thus we have proved' that puttig A(1) AT = 1 log + y + o(.) we have a (Ó) lim PM)(C) = e_e Y (- - y + -) - - I the preset paper we cosider the evolutio of a radom graph i a more systematicc maer ad try to describe the gradual developmet ad step-by-step uravellig of the complex structure of the graph F.,N whe N icreases while is a give large umber. We succeeded i revealig the emergece of certai structural properties of -V N. However a great deal remais to be doe i this field. We shall call i 10. the attetio of the reader to certai usolved problems. It seems to us further that it would be worth while to cosider besides graphs also more complex structures from the same poit of view, i. e. to ivestigate the laws goverig their evolutio i a similar spirit. This may be iterestig ot oly from a purely mathematical poit of view. I fact, the evolutio of graphs may be cosidered as a rather simplified model of the evolutio of certai commuicatio ets (railway, road or electric etwork systems, etc.) of a coutry or some other uit. (Of course, if oe aims at describig such a real situatio, oe should replace the hypothesis of equiprobability of all coectios by some more realistic hypothesis.) It seems plausible that by cosiderig the radom growth of more complicated structures (e. g. structures cosistig of differet sorts of poits ad coectios of differet types) oe could obtai fairly reasoable models of more complex real growth processes (e. g. i Partial result o this problem has bee obtaied already i 1939 by P. ERDős ad 11. WHITNEY but their results have ot bee published. * 0 ERDÖS-RÉNYI the growth of a complex commuicatio et cosistig of differet types of coectios, ad eve of orgaic structures of livig matter, etc.) cotai the discussio of the presece of certai compoets i a radom graph, while 4-9. ivestigate certai global properties of a radom graph. Most of our ivestigatios deal with the case whe N() - e with c 0. I fact our results give a clear picture of the evolutio of r N() whe c = N() (which plays i a certai sese the role of time) icreases. I 10. we make some further remarks ad metio some usolved problems. Our ivestigatio belogs to the combiatorical theory of graphs, which has a fairly large literature. The first who eumerated the umber of possible graphs with a give structure was A. CaYLEY [1]. Next the importat paper [] of G. PÓLYA has to be metioed, the startig poit of which were some chemical problems. Amog more recet results we metio the papers of G. E. UHLENBEcK ad G. W. FORD [5] ad E. N. GILBERT [G]. A fairly complete bibliography will be give i a paper of F. HaRARY [8]. I these papers the probabilistic poit of view was ot explicitly emphasized. This has bee doe i the paper [9] of oe of the authors, but the aim of the probabilistic treatmet was there differet : the existece of certai types of graphs has bee show by provig that their probability is positive. Radom trees have bee cosidered i [ 14]. I a recet paper [10] T. L. AusTIN, R. E. FAGEN, W. F. PENNEY ad J. RioRDAN deal with radom graphs from a poit of view similar to ours. The differece betwee the defiitio of a radom graph i [10] ad i the preset paper cosists i that i [10] it is admitted that two poits should be coected by more tha oe edge ( parallel edges). Thus i [10] it is supposed that after a certai umber of edges have already bee selected, the ext edge to be selected may be ay of the possible edges betwee l 1 the give poits (icludig the edges already selected). Let us deote such a radom graph by I N. The differece betwee the probable properties of r N resp, r,n are i most (but ot i all) cases egligible. The correspodig probabilities are i geeral (if the umber N of edges is ot too large) asymptotically equal. There is a third possible poit of view which is i most cases almost equivalet with these two ; we may suppose that for each pair of give poits it is determied by a chace process whether the edge coectig the two poits should be selected or ot, the probability for selectig ay give edge beig equal to the same umber p 0, ad the decisios cocerig the differet edges beig completely idepedet. I this case of course the umber of edges is a radom variable, hayig the expectatio (l p ; thus if we wat to obtai by this method a radom graph havig i the mea N edges we have to choose the value of p equal to N. We shall deote such a radom graph by F, N. I may (though ot all) of the problems treated i the preset paper it does ot cause ay essetial differece if we cosider istead of r N the radom graph Q*X,. f~l ON THE EVOLUTION OF RANDOM GRAPHS 1 Comparig the method of the preset paper with that of [10] it should be poited out that our aim is to obtai threshold fuctios resp. distributios, ad thus we are iterested i asymptotic formulae for the probabilities cosidered. Exact formulae are of iterest to us oly so far as they help i determiig the asymptotic behaviour of the probabilities cosidered (which is rarely the case i this field, as the exact formulae are i most cases too complicated). O the other had i [10] the emphasis is o exact formulae resp. o geeratig fuctios. The oly exceptio is the average umber of coected compoets, for the asymptotic evaluatio of which a way is idicated i 5. of [10] ; this questio is however more fully discussed i the preset paper ad our results go beyod that of [10]. -Moreover, we cosider ot oly the umber but also the character of the compoets. Thus for istace we poit out the remarkable chage occurig at N -. If L-' - e with c 1/ the with probability tedig to 1 for + - all poits except a bouded umber of poits of r,n belog to compoets which are trees, while for N tit with c 1 this is o loger the case. Further for a fixed value of the average umber of compoets of r,n decreases asymptotically i a liear maer with N, whe N : , while for N the formula givig the average umber of compoets is ot liear i N. I what follows we shall make use of the symbols O ad o. As usually li a() = a (b()) (where b() 0 for = 1,,...~ meas that Mim b()l - 0, -+while a() = 0 (b()) meas that la()j. is bouded. The parameters o b() which the boud of ja() 1 may deped will be idicated if it is ecessary ; b() sometimes we will idicate it by a idex. Thus a() = 0, (b()) meas that ~a()i K(E) where K(E) is a positive costat depedig o e. We write b() a() -b() to deote that Mim a() = b() We shall use the followig defiitios from the theory of graphs. (For the geeral theory see [3] ad [4].) A fiite o-empty set V of labelled poits P l, Pi..., P ad a set E of differet uordered pairs (P;, Pj) with P1 E V, Pi E V, i j is called a graph ; we deote it sometimes by G = {V, E} ; the umber is called the order (or size) of the graph ; the poits Pl, P,..., P are called the vertices ad the pairs (Pi, Pj) the edges of the graph. Thus we cosider o-orieted fiite graphs without parallel edges ad without sligs. The set E may be empty, thus a collectio of poits (especially a sigle poit) is also a graph. A graph G - {V, E } is called a subgraph of a graph Gl = {Vl, El } if the set of vertices V of G Ms a subset of the set of vertices V, of G l ad the set EZ of edges of G is a subset of the set El of edges of G I. ERDŐS-RÉNYi A sequece of k edges of a graph such that every two cosecutive edges ad oly these have a vertex i commo is called a path of order k. A cyclic sequece of k edges of a graph such that every two cosecutive edges ad oly these have a commo vertex is called a cycle of order k. A graph G is called coected if ay two of its poits belog to a path which is a subgraph of G. A graph is called a tree of order (or size) k if it has k vertices, is coected ad if oe of its subgraphs is a cycle. A tree of order k has evidetly k - 1 edges. A graph is called a complete graph of order ~, if it has k vertices ad edges. Thus i a complete graph of order k ay two poits are coected by a edge. A subgraph G' of a graph G will be called a isolated subgraph if all edges of G oe or both edpoits of which belog to G', belog to G'. A coected isolated subgraph G' of a graph G is called a compoet of G. The umber of poits belogig to a compoet G' of a graph G will be called the size of G'. Two graphs shall be called isomorphic, if there exists a oe-to-oe mappig of the vertices carryig over these graphs ito aother. The graph G shall be called complemetary graph of G if G cosists of the same vertices Pl, P,.... P as G ad of those ad oly those edges (P ;, Pj ) which do ot occur i G. The umber of edges startig from the poit P of a graph G will be called the degree of P i G. A graph G is called a saturated eve graph of type (a, b) if it cosists of a + b poits ad its poits ca be split i two subsets V, ad V cosistig of a resp. b poits, such that G cotais ay edge (P, Q) with P E V, ad Q E V ad o other edge. A graph is called plaar, if it ca be draw o the plae so that o two of its edges itersect. We itroduce further the followig defiitios : If a graph G has vertices ad N edges, we call the umber N the degree of the graph. V (As a matter of fact 1ti is the average degree of the vertices of G.) If a graph G has the property that G has o subgraph havig a larger degree tha G itself, we call G a balaced graph. We deote by P (... ) the probability- of the evet i the brackets, by M(~) resp. D (á) the mea value resp. variace of the radom variable s. I cases whe it is ot clear from the cotext i which probability space the probabilities or respectively the mea values ad variaces are to be uderstood, this will be explicitly idicated. Especially M,N resp. D,N will deote the mea value resp. variace calculated with respect to the probabilities P.N ON THE EVOLUTION OF RANDOM GRAPHS 3 (7) We shall ofte use the followig elemetary asymptotic formula : i! k e k'- 0 6= valid for k = o('l=). k Our thaks are due to T. GALLAI for his valuable remarks. 1. Thresholds for subgraphs of give type If N is very small compared with, amely if N - o (V) the it is very probable that r.n is a collectio of isolated poits ad isolated edges, i. e. that o two edges of r,n have a poit i commo. As a matter of fact the probability that at least two edges of r,n shall have a poit i commo is by (7) clearly N) 1-~. ( =0 (1T lj 1' Y1 If however íl c I/I where c 0 is a costat ot depedig o., the the appearace of trees of order 3 will have a probability which teds to a positive limit for -* + -, but the appearace of a coected compoet cosistig of more tha 3 poits will be still very improbable. If N is icreased while is fixed, the situatio will chage oly if N reaches the order of magitude of j3. The trees of order 4 (but ot of higher order) will appear with a probability ot tedig to 0. I geeral, the threshold fuctio for the presece k- of trees of order k is k -1 (k = 3, 4,... ). This result is cotaied i the followig Theorem 1. Let k _ ad l (k - 1 Z _ l 9 lk I be positive itegers. Let k deote a arbitrary ot empty class of coected balaced graphs cosistig of k poits ad l edges. The threshold fuctio for the property that the radom graph cosidered should cotai at least oe subgraph isomorphic with some ele- - k met of y k,, is t. The followig special cases are worth metioig Corollary 1. The threshold fuctio for the property that the radom graph k- cotais a subgraph which is a tree of order k is k - I (k: = 3, ). Corollary. The threshold fuctio for the property that a graph cotais a coected subgraph cosistig of k _ 3 poits ad k edges (i. e. cotaiig exactly oe cycle) is, for each value of k. Corollary 3. The threshold fuctio for the property that a graph cotais a cycle of order k is, for each value of k _ _. 3. 4 ERDŐS-RÉNYI Corollary 4. The threshold fuctio for the property that a graph cotais - 1 ) a complete subgraph of order k _ 3 is z (i k-1,. Corollary 5. The threshold fuctio for the property that a graph cotais a saturated eve subgraph of type (a, b) (i. e. a subgraph cosistig of a + b a+b poits P1,..., Pa, Q I,... Q b ad of the ab edges (P1, Qj ) is ab. To deduce these Corollaries oe has oly to verify that all 5 types of graphs figurig i Corollaries 1-5. are balaced, which is easily see. Proof of Theorem 1. Let Bk I _ 1 deote the umber of graphs belogig to the class which ca be formed from k give labelled poits. Clearly if P,N (&k,l) deotes the probability that the radom graph r,n cotais at least oe subgraph isomorphic with some elemet of the class ^Vjk,l, the P,N(&k,l) k Bk,1 7- l = o ( ` 1-k I J 1 N As a matter of fact if we select k poits (which ca be doe i 171 differet ways) ad form from them a graph isomorphic with some elemet of the class 66k,í (which ca be doe i B k,l differet ways) the the umber of graphs G,N which cotai the selected graph as a subgraph is equal to the umber of ways the remaiig N-1 edges ca be selected from the I other - l possible edges. (Of course those graphs, which cotai more subgraphs isomorphic with some elemet of are couted more tha oce.) k,1 k Now clearly if N = o(_ 1 ) the by P,N( k,l) = O(1) which proves the first part of the assertio of Theorem 1. To prove the secod part of the theorem let -Vki deote the set of all subgraphs of the complete graph cosistig of poits, isomorphic with some elemet of 56 k 1. To ay SE& let us associate a radom variable e(s) such that E(S) = 1 or e(s) = 0 accordig to whether S is a subgraph of P N or ot. The clearly (we write i what follows for the sake of brevity W istead of M,N) (1.) M (~ E(S)1 = M(E(S)) _ () Bk l N - l, Bk,l ( N)'. () () k k I 1-k SE, ik 1 S E.9 ik,1 ~9 l ON THE EVOLUTION OF RANDOM GRAPHS 5 O the other had if SI ad S are two elemets of Z01)1 ad if Sl ad 8 do ot cotai a commo edge the fj -l M(E(SI) E(S» = N-1,~ If S,_ ad S cotai exactly s commo poits ad r commo edges (1 r l -1) we have ~ N, -1+r j l M(s(Sl ) E(S)) -. N r - N1-r 0 f41-r (l N O the other had the itersectio of S I ad S beig a subgraph of S I (ad S ) by our suppositio that each S is balaced, we obtai r l i. e. s z rk S - k l ad thus the umber of such pairs of subgraphs S I ad S does ot exceed Thus we obtai k k -k k _rk 0 B `k kf k-~~ 1. Jz i SE M (~E M(e(S)) +! Bk,1 k!( - k)! i k, 1 ) E(S)~~) k,1-1 ~' N 1 l 1 ;}T k (- 1 +OI N1 J N r ~ Now clearly I 1-1 -l ~ lj! N -1 N-1 k! ( - k)! ' ~k ~I ~1 1 - k 6 ERDŐS--RÉNYI If we suppose that it follows that we have (1.4) I\\\ (Z r SE&( D 1 1 SEM () e(s}) =0 ( k,1 M(8 (8» CU It follows by the iequality of Chebysheff that ad thus P,N Í Z e(s) - Z M( (S)) 1. M(e(S» SE ffi k,1 SEM k,1 setik,1 (1.5) P,N L e(s) 1 M(E(S») =O SEM (r' ), SE Y~kj l1 GJ As clearly by (1.) if w -~ + the M(e(S)) + - it follows ot oly that the probability that 1' cotais at least oe subgraph isomorphic with a elemet of k,i teds to 1, but also that with probability tedig to 1 the umber of subgraphs of F N isomorphic to some elemet of ti 1 ; 1 will ted to +O with the same order of magitude as GJ 1. Thus Theorem 1 is proved. It is iterestig to compare the thresholds for the appearace of a subgraph of a certai type i the above sese with probability ear to 1, with the umber of edges which is eeded i order that the graph should have ecessarily a subgraph of the give type. Such -compulsory thresholds have bee cosidered by P. TURÁN [11] (see also [1]) ad later by P. ERDŐS ad A. 11. STONE [ 17 ]). For istace for a tree of order k clearly the compulsory - ] threshold is I (k ) + 1 ; for the presece of at least oe cycle the compulsory threshold is while accordig to a theorem of P. TURÁN [11] for complete subgraphs of order k the compulsory threshold is (k?) ( - r ) + (k - 1) -v where r=-- (k-- 1) ~- I the paper [13] of T. KŐVÁ RI, ~1 Is - 11' V. T. Sós ad P. TuRÁN it has bee show that the compulsory threshold for the presece
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks