## 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 language | English (US) |
---|---|

Pages (from-to) | 101-114 |

Number of pages | 14 |

Journal | Random Structures and Algorithms |

Volume | 32 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2008 |

## Keywords

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

## ASJC Scopus subject areas

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