The isoperimetric constant of the random graph process

The isoperimetric constant of a graph G on n vertices, i(G), is the minimum of as, vertical bar partial derivative s vertical bar/vertical bar s vertical bar, taken over all nonempty subsets S subset of V(G) of size at most n/2, where aS denotes the set of edges with precisely one end in S. A random graph process on n vertices, (G) over tilde (t), is a sequence of ((n)(2)) graphs, where (G) over tilde (0) is the edgeless graph on n vertices, and (G) over tilde (t) is the result of adding an edge to G(t - 1), uniformly distributed over all the missing edges. The authors show that in almost every graph process i (G) over tilde (t)) equals the minimal degree of (G) over tilde (t) as long as the minimal degree is o(logn). Furthermore, it is shown that this result is essentially best possible, by demonstrating that along the period in which the minimum degree is typically Theta(log n), the ratio between the isoperimetric constant and the minimum degree falls from 1 to 1/2, its final value. (c) 2007 Wiley Periodicals, Inc.