4
$\begingroup$

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!

  • 1
    Not sure if it addresses all your questions, but you should check out Peter Sarnak's [What is an expander?](http://www.ams.org/notices/200407/what-is.pdf)2012-12-08
  • 0
    Thanks, @dan! Is it correct that the expansion (the quantity) has nothing to do with the sparseness of the graph, does it?2012-12-09
  • 0
    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$.2018-05-07

1 Answers 1