THE BIRTH OF THE GIANT COMPONENT

Limiting distributions are derived for the sparse connected components that are present when a random graph on n vertices has approximately 1/2n edges. In particular, we show that such a graph consists entirely of trees, unicyclic components, and bicyclic components with probability approaching square root 2/3 cosh square root 5/18 almost-equal-to 0.9325 as n --> infinity. The limiting probability that it 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/2n, 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 5pi/18 almost-equal-to 0.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 Erdos and Renyi. 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.