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.
- "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?
- Do the edge and vertex expansions measure how good a expander is, and/or how connected a graph is, and/or something else?
- 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!