| The isoperimetric constant of the random graph process, preprint (2008) | |||||||||||||||
Abstract | |||||||||||||||
| 2\Delta graphs, where eG(0) is the edgeless graph on n vertices, and eG(t) is the result of addingan edge to e G(t- 1), uniformly distributed over all the missing edges. We show that in almost every graph process i ( eG(t)) equals the minimal degree of eG(t) as long as the minimal degree is o(log n). Furthermore, we show 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 12, its final value. 1 Introduction Let G = (V, E) be a graph. For each subset of its vertices, S ` V, we define its edge boundary, @S, as the set of all edges with exactly one endpoint in S: | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||