A CRITICAL-POINT FOR RANDOM GRAPHS WITH A GIVEN DEGREE SEQUENCE

Given a sequence of nonnegative real numbers lambda(0), lambda(1),... which sum to 1, we consider random graphs having approximately hin vertices of degree i. Essentially, we show that if Sigma i(i - 2)lambda(i) > 0, then such graphs almost surely have a giant component, while if Sigma i(i - 2)lambda(i) < 0, then almost surely all components in such graphs are small. We can apply these results to G(n,p), G(n,M), and other well-known models of random graphs. There are also applications related to the chromatic number of sparse random graphs. (C) 1995 John Wiley & Sons, Inc.