# Expander graph

 related topics {math, number, function} {rate, high, increase} {system, computer, user} {household, population, female} {math, energy, light}

In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.[1]

## Contents

### Definitions

There are several different ways to measure the expansion properties of a finite, undirected multigraph G.

### Edge expansion

The edge expansion (also isoperimetric number or Cheeger constant) h(G) of a graph G is defined as

where the minimum is over all nonempty sets S of at most n / 2 vertices and $\partial(S)$ is the edge boundary of S, i.e., the set of edges with exactly one endpoint in S.[2] It is closely related to the conductance.[citation needed]