[Math] Meanings of expansion and expander

graph theory

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!

Best Answer

From Graph Theory by Hall:

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$.

To answer parts two and three of your question:

  1. Edge/vertex expansion is a measure of how evenly you can divide a graph in two. Intuitively you might try to use the minimum cut or a cut which partitions the nodes into two roughly equal sized pieces but there exists graphs for which these heuristics perform poorly. The edge expansion is sort of a combination of these two heuristics. A graph with small edge expansion has a cut with few crossing edges and divides the vertices approximately in-half. See the OCW course Topics in Theoretical Computer Science: An Algorithmist's Toolkit (Lecture 3) for more detail (what the lecturer calls cut-ratio is essentially the same as edge expansion; it just hasn't been normalized).
  2. Hopefully you see how the degree figures into the discussion now from the definition. To get the edge expansion you have to divide by the degree (typically when we talk about expansions, our underlying graph is regular).
Related Question