# Meanings of expansion and expander?

From Wikipedia

Intuitively, an expander is a finite, undirected multigraph in which every subset of the vertices "which is not too large" has a "large" boundary. Different formalisations of these notions give rise to different notions of expanders: edge expanders, vertex expanders, and spectral expanders, as defined below.

A disconnected graph is not an expander, since the boundary of a connected component is empty. Every connected graph is an expander; however, different connected graphs have different expansion parameters. The complete graph has the best expansion property, but it has largest possible degree. Informally, a graph is a good expander if it has low degree and high expansion parameters.

Edge expansion

The edge expansion (also isoperimetric number or Cheeger constant) h(G) of a graph G on n vertices is defined as $$h(G) = \min_{0 < |S| \le \frac{n}{2} } \frac{|\partial(S)|}{|S|}\,,$$ 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.

Vertex expansion

The vertex isoperimetric number $h_{\text{out}}(G)$ (also vertex expansion or magnification) of a graph G is defined as $$h_{\text{out}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|}\,,$$

where $\partial_{\text{out}}(S)$ is the outer boundary of S, i.e., the set of vertices in $V(G)\setminus S$ with at least one neighbor in S.

1. "an expander is a finite, undirected multigraph in which every subset of the vertices which is not too large has a large boundary." How is an expander formally defined?
2. Do the edge and vertex expansions measure how good a expander is, and/or how connected a graph is, and/or something else?
3. How are the edge and vertex expansions related to the degrees, as in "a graph is a good expander if it has low degree and high expansion parameters"?

Thanks and regards!

• Not sure if it addresses all your questions, but you should check out Peter Sarnak's What is an expander?
– user52274
Dec 8 '12 at 20:41
• Thanks, @dan! Is it correct that the expansion (the quantity) has nothing to do with the sparseness of the graph, does it?
– Tim
Dec 9 '12 at 0:01
• The expansion is actually quite similar to the sparsest cut in a graph. For a $d$-regular graph $G = (V,E)$ with $|V| = n$, the sparsity of a cut $S$ is defined as $$\phi(S) = \frac{E(S, V-S)}{\frac{d}{n}\cdot|S|\cdot|V-S|}$$ where $E(S,V-S)$ is the number of edges crossing the cut. The sparsest cut, $\phi(G)$, is the minimum $\phi(S)$ over all subsets $S \subseteq V$. May 7 '18 at 21:27

An $(n,k,c)$-expander is an $X,Y$-bipartite graph $G$ with $|X| = |Y| = n$ such that $\Delta(G) \leq k$ and that $|N(S)| \geq (1 + c(1-|S|/n))\cdot |S|$ for every $S \subseteq X$ with $|S| \leq n/2$.
Here Hall uses $\Delta(G)$ to represent the maximum degree in $G$ and $N(S)$ to represent the neighbour set of $S \subseteq V$.