THE STRUCTURE OF A RANDOM GRAPH AT THE POINT OF THE PHASE-TRANSITION

Consider the random graph models G(n, #edges = M) and G(n, Prob(edge) = p) with M = M(n) = (1 + lambdan-1/3)n/2 and p = p(n) = (1 + lambdan- 1/3)/n. For l greater-than-or-equal-to -1 define an l-component of a r andom graph as a component which has exactly l more edges than vertice s. Call an 1-component with l greater-than-or-equal-to 1 a complex com ponent. For both models, we show that when lambda is constant, the exp ected number of complex components is bounded, almost surely (a.s.) ea ch of these components (if any exist) has size of order n2/3, and the maximum value of 1 is bounded in probability. We prove that a.s. the l argest suspended tree in each complex component has size of order n2/3 , and deletion of all suspended trees results in a 'smoothed'' graph o f size of order n1/3, with the maximum vertex degree 3. The total numb er of branching vertices, i.e., of degree 3, is bounded in probability . Thus, each complex component is almost surely topologically equivale nt to a 3-regular multigraph of a uniformly bounded size. Lengths of t he shortest cycle and of the shortest path between two branching verti ces of a smoothed graph are each of order n1/3. We find a relatively s imple integral formula for the limit distribution of the numbers of co mplex components, which implies, in particular, that all values of the 'complexity spectrum'' have positive limiting probabilities. We also answer questions raised by Erdos and Renyi back in 1960. It is proven that there exists p(lambda) , the limiting planarity probability, with 0 < p(lambda) < 1, p(-infinity) = 1, p(infinity) = 0. In particular, G(n, M) (G(n, p), resp.) is almost surely nonplanar iff (M - n/2)n-2/3 --> infinity ((np - 1)n-1/3) --> infinity, resp.).