The structure of a random graph at the point of the phase transition
Authors:
 Tomasz Łuczak,
 Boris Pittel,
 John C. Wierman
Abstract
Consider the random graph models and G(n, Prob(edge) = p) with and define an /component of a random graph as a component which has exactly more edges than vertices. Call an /component with 1 a complex component. For both models, we show that when A 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 n2/3, and deletion of all suspended trees results in a "smoothed" graph of size of order n1'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 3regular 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 n1/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(k), the limiting planarity probability, with. In particular, G(n, M) (G(n, p), resp.) is almost surely nonplanar iff (resp.). © 1994 American Mathematical Society.
 Record ID
 UAM8f8fb7bbc54245688c968064eb897003
 Author
 Journal series
 Transactions of the American Mathematical Society, ISSN 00029947
 Issue year
 1994
 Vol
 341
 No
 2
 Pages
 721748
 ASJC Classification
 ;
 DOI
 DOI:10.1090/S00029947199411389505 Opening in a new tab
 URL
 https://www.ams.org/journals/tran/199434102/S00029947199411389505/home.html Opening in a new tab
 Language
 (en) English
 File

 File: 1
 S00029947199411389505.pdf

 Score (nominal)
 0
 Score source
 journalList
 Publication indicators
 = 76; = 73; = 164; : 1999 = 1.449; : 2006 (2 years) = 0.820  2007 (5 years) =0.961
 Citation count
 164
 Uniform Resource Identifier
 https://researchportal.amu.edu.pl/info/article/UAM8f8fb7bbc54245688c968064eb897003/
 URN
urn:amuprod:UAM8f8fb7bbc54245688c968064eb897003
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.