The birth of the giant component
| dc.creator | Janson, Svante | |
| dc.creator | Knuth, Donald E. | |
| dc.creator | Łuczak, Tomasz | |
| dc.creator | Pittel, Boris | |
| dc.date | 1993-10-01 | |
| dc.date.accessioned | 2026-07-07T09:14:59Z | |
| dc.date.available | 2026-07-07T09:14:59Z | |
| dc.description | Limiting distributions are derived for the sparse connected components that are present when a random graph on $n$ vertices has approximately $\half n$ edges. In particular, we show that such a graph consists entirely of trees, unicyclic components, and bicyclic components with probability approaching $\sqrt{2\over 3} \cosh\sqrt{5\over 18}\approx0.9325$ as $n\to\infty$. The limiting probability that it consists of trees, unicyclic components, and at most one other component is approximately 0.9957; the limiting probability that it is planar lies between 0.987 and 0.9998. When a random graph evolves and the number of edges passes $\half n$, its components grow in cyclic complexity according to an interesting Markov process whose asymptotic structure is derived. The probability that there never is more than a single component with more edges than vertices, throughout the evolution, approaches $5π/18\approx0.8727$. A ``uniform'' model of random graphs, which allows self-loops and multiple edges, is shown to lead to formulas that are substantially simpler than the analogous formulas for the classical random graphs of Erdős and Rényi. The notions of ``excess'' and ``deficiency,'' which are significant characteristics of the generating function as well as of the graphs themselves, lead to a mathematically attractive structural theory for the uniform model. A general approach to the study of stopping configurations makes it possible to sharpen previously obtained estimates in a uniform manner and often to obtain closed forms for the constants of interest. Empirical results are presented to complement the analysis, indicating the typical behavior when $n$ is near 20000. | |
| dc.identifier | https://arxiv.org/abs/math/9310236 | |
| dc.identifier | http://arxiv.org/abs/math/9310236 | |
| dc.identifier | Random Structures Algorithms 4 (1993), no. 3, 231--358 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/152876 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.title | The birth of the giant component | |
| dc.type | text |