The structure of a random graph at the point of the phase transition
HTML articles powered by AMS MathViewer
- by Tomasz Łuczak, Boris Pittel and John C. Wierman PDF
- Trans. Amer. Math. Soc. 341 (1994), 721-748 Request permission
Abstract:
Consider the random graph models $G(n,\# \;{\text {edges}} = M)$ and $G(n,\operatorname {Prob}({\text {edge}}) = p)$ with $M = M(n) = (1 + \lambda {n^{ - 1/3}})n/2$ and $p = p(n) = (1 + \lambda {n^{ - 1/3}})/n$. For $l \geq - 1$ define an $l$-component of a random graph as a component which has exactly $l$ more edges than vertices. Call an $l$-component with $l \geq 1$ a complex component. For both models, we show that when $\lambda$ 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 ${n^{2/3}}$, and the maximum value of $l$ is bounded in probability. We prove that a.s. the largest suspended tree in each complex component has size of order ${n^{2/3}}$, and deletion of all suspended trees results in a "smoothed" graph of size of order ${n^{1/3}}$, with the maximum vertex degree $3$. The total number of branching vertices, i.e., of degree $3$, is bounded in probability. Thus, each complex component is almost surely topologically equivalent to a $3$-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 ${n^{1/3}}$. 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 $p(\lambda )$, the limiting planarity probability, with $0 < p(\lambda ) < 1$, $p( - \infty ) = 1$, $p(\infty ) = 0$. In particular, $G(n,M)\quad (G(n,p),{\text {resp}}.)$ is almost surely nonplanar iff $(M - n/2){n^{ - 2/3}} \to \infty \;((np - 1){n^{ - 1/3}}) \to \infty ,{\text {resp}}.)$.References
- 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, DOI 10.1016/0022-0000(79)90045-X
- 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, DOI 10.1002/rsa.3240010202
- Béla Bollobás, The evolution of random graphs, Trans. Amer. Math. Soc. 286 (1984), no. 1, 257–274. MR 756039, DOI 10.1090/S0002-9947-1984-0756039-5 —, 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. 35-37.
- Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. MR 809996
- 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. 5-6, 387–394. MR 954351, DOI 10.1007/BF01158847
- 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 125031
- Philippe Flajolet, Donald E. Knuth, and Boris Pittel, The first cycles in an evolving graph, Discrete Math. 75 (1989), no. 1-3, 167–215. Graph theory and combinatorics (Cambridge, 1988). MR 1001395, DOI 10.1016/0012-365X(89)90087-3
- Geoffrey Grimmett, Random graphs, Selected topics in graph theory, 2, Academic Press, London, 1983, pp. 201–235. MR 797253
- Svante Janson, Poisson approximation for large deviations, Random Structures Algorithms 1 (1990), no. 2, 221–229. MR 1138428, DOI 10.1002/rsa.3240010209
- MichałKaroński, A review of random graphs, J. Graph Theory 6 (1982), no. 4, 349–389. MR 679594, DOI 10.1002/jgt.3190060402 D. E. Knuth, Private communication.
- 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
- T. Łuczak and J. C. Wierman, The chromatic number of random graphs at the double-jump threshold, Combinatorica 9 (1989), no. 1, 39–49. MR 1010298, DOI 10.1007/BF02122682
- Tomasz Łuczak, Component behavior near the critical point of the random graph process, Random Structures Algorithms 1 (1990), no. 3, 287–310. MR 1099794, DOI 10.1002/rsa.3240010305
- J. W. Moon, Counting labelled trees, Canadian Mathematical Monographs, No. 1, Canadian Mathematical Congress, Montreal, Que., 1970. From lectures delivered to the Twelfth Biennial Seminar of the Canadian Mathematical Congress (Vancouver, 1969). MR 0274333
- Edgar M. Palmer, Graphical evolution, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1985. An introduction to the theory of random graphs; A Wiley-Interscience Publication. MR 795795 Yu. L. Pavlov, The asymptotic distribution of maximum tree size in a random forest, Theory Probab. Appl. 22, 509-520. —, A case of limit distribution of the maximal volume of a tree in a random forest, Math. Notes 25, 387-392.
- 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, DOI 10.1017/S0305004100060205
- V. E. Stepanov, The probability of the connectedness of a random graph ${\cal G}_{m}\,(t)$, Teor. Verojatnost. i Primenen 15 (1970), 58–68 (Russian, with English summary). MR 0270406 —, On the probability of connectedness of a random graph ${G_m}(t)$, Theory Probab. Appl. 15, 55-67. —, On some features of the structure of a random graph near a critical point, Theory Probab. Appl. 32, 573-594.
- V. A. Voblyĭ, Wright and Stepanov-Wright coefficients, Mat. Zametki 42 (1987), no. 6, 854–862, 911 (Russian). MR 934817
- E. M. Wright, The number of connected sparsely edged graphs, J. Graph Theory 1 (1977), no. 4, 317–330. MR 463026, DOI 10.1002/jgt.3190010407
- E. M. Wright, The number of connected sparsely edged graphs. III. Asymptotic results, J. Graph Theory 4 (1980), no. 4, 393–407. MR 595607, DOI 10.1002/jgt.3190040409
Additional Information
- © Copyright 1994 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 341 (1994), 721-748
- MSC: Primary 05C80; Secondary 60C05
- DOI: https://doi.org/10.1090/S0002-9947-1994-1138950-5
- MathSciNet review: 1138950