The isoperimetric constant of the random graph process

Itai Benjamini, Simi Haber, Michael Krivelevich, Eyal Lubetzky

Research output: Contribution to journalArticlepeer-review


The isoperimetric constant of a graph G on n vertices, i(G), is the minimum of (Equation Presented), 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, G̃(t), is a sequence of (Equation Presented) graphs, where G̃(0) is the edgeless graph on n vertices, and G̃(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̃(t)) equals the minimal degree of 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/2, its final value.

Original languageEnglish (US)
Pages (from-to)101-114
Number of pages14
JournalRandom Structures and Algorithms
Issue number1
StatePublished - Jan 2008


  • Conductance
  • Isoperimetric constant
  • Minimal degree
  • Random graph process

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'The isoperimetric constant of the random graph process'. Together they form a unique fingerprint.

Cite this