The structure of a random graph at the point of the phase transition
Authors:
Tomasz Łuczak, Boris Pittel and John C. Wierman
Journal:
Trans. Amer. Math. Soc. 341 (1994), 721748
MSC:
Primary 05C80; Secondary 60C05
MathSciNet review:
1138950
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Consider the random graph models and with and . For define an component of a random graph as a component which has exactly more edges than vertices. Call an component with a complex component. For both models, we show that when is constant, the expected number of complex components is bounded, almost surely (a.s.) each of these components (if any exist) has size of order , and the maximum value of is bounded in probability. We prove that a.s. the largest suspended tree in each complex component has size of order , and deletion of all suspended trees results in a "smoothed" graph of size of order , with the maximum vertex degree . The total number of branching vertices, i.e., of degree , is bounded in probability. Thus, each complex component is almost surely topologically equivalent to a regular multigraph of a uniformly bounded size. Lengths of the shortest cycle and of the shortest path between two branching vertices of a smoothed graph are each of order . We find a relatively simple integral formula for the limit distribution of the numbers of complex components, which implies, in particular, that all values of the "complexity spectrum" have positive limiting probabilities. We also answer questions raised by Erdös and Rényi back in 1960. It is proven that there exists , the limiting planarity probability, with , , . In particular, is almost surely nonplanar iff .
 [1979]
D.
Angluin and L.
G. Valiant, Fast probabilistic algorithms for Hamiltonian circuits
and matchings, J. Comput. System Sci. 18 (1979),
no. 2, 155–193. MR 532174
(80f:68040), http://dx.doi.org/10.1016/00220000(79)90045X
 [1990]
Edward
A. Bender, E.
Rodney Canfield, and Brendan
D. McKay, The asymptotic number of labeled connected graphs with a
given number of vertices and edges, Random Structures Algorithms
1 (1990), no. 2, 127–169. MR 1138421
(92i:05108), http://dx.doi.org/10.1002/rsa.3240010202
 [1984a]
Béla
Bollobás, The evolution of random
graphs, Trans. Amer. Math. Soc.
286 (1984), no. 1,
257–274. MR
756039 (85k:05090), http://dx.doi.org/10.1090/S00029947198407560395
 [1984b]
, The evolution of sparse random graphs, Graph Theory and Combinatorics (Proc. Cambridge Combinatorial Conf. in Honour of Paul Erdös), Academic Press, San Diego, CA, pp. 3537.
 [1985]
Béla
Bollobás, Random graphs, Academic Press, Inc. [Harcourt
Brace Jovanovich, Publishers], London, 1985. MR 809996
(87f:05152)
 [1988]
V.
E. Britikov, Asymptotics of the number of forests made up of
nonrooted trees, Mat. Zametki 43 (1988), no. 5,
672–684, 703 (Russian); English transl., Math. Notes
43 (1988), no. 56, 387–394. MR 954351
(89j:05063), http://dx.doi.org/10.1007/BF01158847
 [1960]
P.
Erdős and A.
Rényi, On the evolution of random graphs, Magyar Tud.
Akad. Mat. Kutató Int. Közl. 5 (1960),
17–61 (English, with Russian summary). MR 0125031
(23 #A2338)
 [1989]
Philippe
Flajolet, Donald
E. Knuth, and Boris
Pittel, The first cycles in an evolving graph, Discrete Math.
75 (1989), no. 13, 167–215. Graph theory and
combinatorics (Cambridge, 1988). MR 1001395
(90d:05184), http://dx.doi.org/10.1016/0012365X(89)900873
 [1980]
Geoffrey
Grimmett, Random graphs, Selected topics in graph theory, 2,
Academic Press, London, 1983, pp. 201–235. MR 797253
(86j:05128)
 [1990]
Svante
Janson, Poisson approximation for large deviations, Random
Structures Algorithms 1 (1990), no. 2, 221–229.
MR
1138428 (93a:60041), http://dx.doi.org/10.1002/rsa.3240010209
 [1982]
Michał
Karoński, A review of random graphs, J. Graph Theory
6 (1982), no. 4, 349–389. MR 679594
(84b:05004), http://dx.doi.org/10.1002/jgt.3190060402
 [1988]
D. E. Knuth, Private communication.
 [1986]
V.
F. Kolchin, The behavior of a random graph near a critical
point, Teor. Veroyatnost. i Primenen. 31 (1986),
no. 3, 503–515 (Russian). MR 866870
(87k:05139)
 [1989]
T.
Łuczak and J.
C. Wierman, The chromatic number of random graphs at the
doublejump threshold, Combinatorica 9 (1989),
no. 1, 39–49. MR 1010298
(91d:05083), http://dx.doi.org/10.1007/BF02122682
 [1990]
Tomasz
Łuczak, Component behavior near the critical point of the
random graph process, Random Structures Algorithms 1
(1990), no. 3, 287–310. MR 1099794
(92c:05139), http://dx.doi.org/10.1002/rsa.3240010305
 [1970]
J.
W. Moon, Counting labelled trees, From lectures delivered to
the Twelfth Biennial Seminar of the Canadian Mathematical Congress
(Vancouver, vol. 1969, Canadian Mathematical Congress, Montreal, Que.,
1970. MR
0274333 (43 #98)
 [1985]
Edgar
M. Palmer, Graphical evolution, WileyInterscience Series in
Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1985. An
introduction to the theory of random graphs; A WileyInterscience
Publication. MR
795795 (87a:05121)
 [1977]
Yu. L. Pavlov, The asymptotic distribution of maximum tree size in a random forest, Theory Probab. Appl. 22, 509520.
 [1979]
, A case of limit distribution of the maximal volume of a tree in a random forest, Math. Notes 25, 387392.
 [1982]
B.
Pittel′, On the probable behaviour of some algorithms for
finding the stability number of a graph, Math. Proc. Cambridge Philos.
Soc. 92 (1982), no. 3, 511–526. MR 677474
(83k:68064), http://dx.doi.org/10.1017/S0305004100060205
 [1970a]
V.
E. Stepanov, Phase transitions in random graphs, Teor.
Verojatnost. i Primenen. 15 (1970), 200–216
(Russian, with English summary). MR 0270407
(42 #5295b)
 [1970b]
, On the probability of connectedness of a random graph , Theory Probab. Appl. 15, 5567.
 [1988]
, On some features of the structure of a random graph near a critical point, Theory Probab. Appl. 32, 573594.
 [1987]
V.
A. Voblyĭ, Wright and StepanovWright coefficients,
Mat. Zametki 42 (1987), no. 6, 854–862, 911
(Russian). MR
934817 (89d:05103)
 [1977]
E.
M. Wright, The number of connected sparsely edged graphs, J.
Graph Theory 1 (1977), no. 4, 317–330. MR 0463026
(57 #2990)
 [1980]
E.
M. Wright, The number of connected sparsely edged graphs. III.
Asymptotic results, J. Graph Theory 4 (1980),
no. 4, 393–407. MR 595607
(82d:05070), http://dx.doi.org/10.1002/jgt.3190040409
 [1979]
 D. Angluin and L. G. Valiant, Fast probabilistic algorithms for Hamilton circuits and matchings, J. Comput. System Sci. 18, 155193. MR 532174 (80f:68040)
 [1990]
 E. A. Bender, E. R. Canfield, and B. D. McKay, The asymptotic number of labeled connected graphs with a given number of vertices and edges, Random Structures & Algorithms 1, 127169. MR 1138421 (92i:05108)
 [1984a]
 B. Bollobás, The evolution of random graphs, Trans. Amer. Math. Soc. 286, 257274. MR 756039 (85k:05090)
 [1984b]
 , The evolution of sparse random graphs, Graph Theory and Combinatorics (Proc. Cambridge Combinatorial Conf. in Honour of Paul Erdös), Academic Press, San Diego, CA, pp. 3537.
 [1985]
 , Random graphs, Academic Press, San Diego, CA. MR 809996 (87f:05152)
 [1988]
 V. E. Britikov, Asymptotic number of forests from unrooted trees, Math. Notes 43, 387394. MR 954351 (89j:05063)
 [1960]
 P. Erdös and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutato Int. Kozl. 5, 1761. MR 0125031 (23:A2338)
 [1989]
 P. Flajolet, D. E. Knuth, and B. Pittel, The first cycles in an evolving graph, Discrete Math. 75, 167215. MR 1001395 (90d:05184)
 [1980]
 G. Grimmett, Random graphs, Further Selected Topics in Graph Theory (L. Beineke and R. J. Wilson, eds.), Academic Press, San Diego, CA. MR 797253 (86j:05128)
 [1990]
 S. Janson, Poisson approximation for large deviations, Random Structures & Algorithms 1, 221229. MR 1138428 (93a:60041)
 [1982]
 M. Karoński, A review of random graphs, J. Graph Theory 6, 349389. MR 679594 (84b:05004)
 [1988]
 D. E. Knuth, Private communication.
 [1986]
 V. F. Kolchin, On the behavior of a random graph near a critical point, Theory Probab. Appl. 31, 439451. MR 866870 (87k:05139)
 [1989]
 T. Luczak and J. C. Wierman, The chromatic number of random graphs at the doublejump threshold, Combinatorica 9, 3949. MR 1010298 (91d:05083)
 [1990]
 T. Luczak, Component behavior near the critical point of the random graph process, Random Structures & Algorithms 1, 287310. MR 1099794 (92c:05139)
 [1970]
 J. W. Moon, Counting labelled trees, Canad. Math. Congress, Montreal. MR 0274333 (43:98)
 [1985]
 E. M. Palmer, Graphical evolution, Wiley, New York. MR 795795 (87a:05121)
 [1977]
 Yu. L. Pavlov, The asymptotic distribution of maximum tree size in a random forest, Theory Probab. Appl. 22, 509520.
 [1979]
 , A case of limit distribution of the maximal volume of a tree in a random forest, Math. Notes 25, 387392.
 [1982]
 B. Pittel, On the probable behavior of some algorithms for finding the stability number of a graph, Math. Proc. Cambridge Philos. Soc. 92, 511526. MR 677474 (83k:68064)
 [1970a]
 V. E. Stepanov, Phase transitions in random graphs, Theory Probab. Appl. 15, 187203. MR 0270407 (42:5295b)
 [1970b]
 , On the probability of connectedness of a random graph , Theory Probab. Appl. 15, 5567.
 [1988]
 , On some features of the structure of a random graph near a critical point, Theory Probab. Appl. 32, 573594.
 [1987]
 V. A. Voblyi, Wright and StepanovWright coefficients, Math Notes 42, 969974. MR 934817 (89d:05103)
 [1977]
 E. M. Wright, The number of connected sparsely edged graphs, J. Graph Theory 1, 317330. MR 0463026 (57:2990)
 [1980]
 , The number of connected sparsely edged graphs. III: Asymptotic results, J. Graph Theory 4, 393407. MR 595607 (82d:05070)
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC:
05C80,
60C05
Retrieve articles in all journals
with MSC:
05C80,
60C05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00029947199411389505
PII:
S 00029947(1994)11389505
Keywords:
Random graph,
planar graph,
threshold function,
limit distribution
Article copyright:
© Copyright 1994
American Mathematical Society
