The isoperimetric constant of the random graph process

Itai Benjamini, Simi Haber, Michael Krivelevich, Eyal Lubetzky

Research output: Contribution to journalArticle

Abstract

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
Volume32
Issue number1
DOIs
StatePublished - Jan 2008

Keywords

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

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

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

  • Cite this