2005/09/01 by Itaï Benjamini, Itai Benjamini, Simi Haber +6
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Opinion Dynamics and Social Influence #Probability (math.PR) #Stochastic processes and statistical mechanics #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.math/0509022
arxiv created 2005/09/01 · openalex publication_date 2005/09/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The isoperimetric constant of a graph G on n vertices, i(G), is the minimum of (|∂ S|)/(|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, \widetildeG(t), is a sequence of \binomn2 graphs, where \widetildeG(0) is the edgeless graph on n vertices, and \widetildeG(t) is the result of adding an edge to \widetildeG(t-1), uniformly distributed over all the missing edges. We show that in almost every graph process i(\widetildeG(t)) equals the minimal degree of \widetildeG(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 Θ(log n), the ratio between the isoperimetric constant and the minimum degree falls from 1 to 1/2, its final value.