Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.