The birth of the giant component

TLDR

Limiting distributions for sparse components in random graphs with about ½ n edges are derived, and the concepts of excess and deficiency underpin a structural theory for the uniform random graph model. The study aims to develop a general approach to stopping configurations that sharpens previous estimates and yields closed‑form constants. They analyze stopping configurations in random graphs using a general framework that yields sharper estimates and closed‑form constants. The analysis shows that a random graph with about ½ n edges almost surely consists of trees, unicyclic, and bicyclic components, with planar probability near 0.99, and that component complexity follows a Markov process; the uniform model yields simpler formulas, and empirical data near n≈2000 confirm the theoretical predictions. © 1993 John Wiley & Sons, Inc.

Abstract

Abstract Limiting distributions are derived for the sparse connected components that are present when a random graph on n vertices has approximately 1/2 n edges. In particular, we show that such a graph consists entirely of trees, unicyclic components, and bicyclic components with probability approaching √2/3 cosh √5/18 ≈ 0.9325 as n →∞. The limiting probability that it is consists of trees, unicyclic components, and at most one another 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 1/2 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 veolution, approaches 5 π/18 ≈ 0.8727. A “uniform” model of random graphs, which allows self‐loops and multiple edges, is shown to lead to formulas that are substanitially 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 2oooO. © 1993 John Wiley & Sons, Inc.