The isoperimetric constant of the random graph process

Abstract

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

Locations

• arXiv (Cornell University) - View - PDF
• Random Structures and Algorithms - View