Expander graph

In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

Definitions

There are several different ways to measure the expansion properties of a finite, undirected multigraph G.

Edge expansion

The edge expansion (also isoperimetric number or Cheeger constant) h(G) of a graph G 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_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. In a variant of this definition (called unique neighbor expansion) $\partial_{\text{out}}(S)$ is replaced by the set of vertices in V with exactly one neighbor in S.^{[citation needed]}

The vertex isoperimetric number h_in(G) of a graph G is defined as

$h_{\text{in}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{in}}(S)|}{|S|}\,,$

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

Spectral expansion

When G is regular, a linear algebraic definition of expansion is possible based on the eigenvalues of the adjacency matrix A = A(G) of G (where A_ii is the number of loops at the ith vertex). Because A is symmetric, the spectral theorem implies that A has n real-valued eigenvalues $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_{n}$. Because G is regular, λ₁ = d where d is the degree of vertices of G. In some contexts, the spectral gap of G is defined to be d − λ₂. In other contexts, the spectral gap is d − λ, where

$\lambda=\max\{|\lambda_2|, |\lambda_{n}|\}. \,$

The normalized version of this definition, where we consider the matrix A / d and get eigenvalues between −1 and 1, is also widely used and more convenient in the statement of some results.

Frequently one will refer to the second-largest eigenvalue of a graph G, which is the max of $\left|\lambda_2\right|$ and $\left|\lambda_{n}\right|$. Depending on the context it may be either the normalized version (taking value between 0 and 1) or the un-normalized version (taking value between 0 and d).

For not necessarily regular graphs, the spectrum of a graph can be defined similarly using its Laplacian matrix.

Expander families

A family $\mathcal{G} = \{G_1, G_2, \ldots \}$ of d-regular graphs is an edge expander family if there is a constant c > 0 such that $h(G) \ge c$ for each $G \in \mathcal{G}$. Typically we want d to be constant, though it is sometimes also interesting to consider d = log  | G | or even d = | G | ^O(1). Similarly, $\mathcal{G}$ is a vertex expander family if there is a constant c > 1 such that $h_{\text{out}}(G) \ge c$ for each $G \in \mathcal{G}$, and $\mathcal{G}$ is a spectral expander family if some positive constant is a lower bound for the spectral gap of each $G \in \mathcal{G}$.

These definitions can be extended to the case of directed graphs.^{[citation needed]} A directed graph can also be interpreted as a balanced bipartite graph (with all edges going from one copy of V to another copy). The definition of bipartite expanders can further be generalized to the case of unbalanced bipartite graphs.^{[citation needed]}

Relationships between different expansion properties

The expansion parameters defined above are related to each other. In particular, for any d-regular graph G,

$h_{\text{out}}(G) \le h(G) \le d \cdot h_{\text{out}}(G)\,.$

Consequently, for constant degree graphs, vertex and edge expansion are qualitatively the same.

Cheeger inequalities

When G is d-regular, there is a relationship between h(G) and the spectral gap d − λ₂ of G. An inequality "due to Cheeger and Buser in the continuous case and to Tanner, Alon, and Milman in the discrete case" states that

$\frac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}\,.$

This inequality is closely related to the Cheeger bound for Markov chains and can be seen as a discrete version of Cheeger's inequality in Riemannian geometry.

Similar connections between vertex isoperimetric numbers and the spectral gap have also been studied:

$h_{\text{out}}(G)\le (\sqrt{2 (d-\lambda_2)} + 1)^2 -1$

$h_{\text{in}}(G) \le 2\cdot \sqrt{d-\lambda_2}$

Asymptotically speaking, the quantities $\frac{h^2}{d}$, h_out, and $h_{\text{in}}^2$ are all upper bounded by the spectral gap O(d − λ₂).

Examples of expanders

A random d-regular graph has good expansion, with high probability. Ramanujan graphs are a family of d-regular expander graphs with d being constant and with explicit constructions, that have essentially the largest possible spectral gap. Algebraic constructions based on Cayley graphs are known for various variants of expander graphs. Most recently, combinatorial constructions of expanders have also been discovered.

Applications and useful properties

The original motivation for expanders is to build economical robust networks (phone or computer): an expander with bounded valence is precisely an asymptotic robust graph with number of edges growing linearly with size (number of vertices), for all subsets.

Expander graphs have found extensive applications in computer science, in designing algorithms, error correcting codes, extractors, pseudorandom generators, sorting networks (Ajtai, Komlós & Szemerédi (1983)) and robust computer networks. They have also been used in proofs of many important results in computational complexity theory, such as SL=L (Reingold (2008)) and the PCP theorem (Dinur (2007)). In cryptography, expander graphs are used to construct hash functions.

The following are some properties of expander graphs that have proven useful in many areas.

Expander mixing lemma

Main article: Expander mixing lemma

The expander mixing lemma states that, for any two subsets of the vertices $S, T \subseteq V$, the number of edges between S and T is approximately what you would expect in a random d-regular graph, i.e. $d |S| \cdot |T| / n$.

Expander walk sampling

Main article: Expander walk sampling

The Chernoff bound states that, when sampling many independent samples from a random variables in the range [ − 1,1], with high probability the average of our samples is close to the expectation of the random variable. The expander walk sampling lemma, due to Ajtai, Komlós & Szemerédi (1987) and Gillman (1998), states that this also holds true when sampling from a walk on an expander graph. This is particularly useful in the theory of derandomization, since sampling according to an expander walk uses much fewer random bits than sampling independently.

See also

• Algebraic connectivity
• Zig-zag product

References

Textbooks and surveys

• Chung, Fan R. K. (1997), Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, 92, American Mathematical Society, ISBN 0-8218-0315-8 
• Davidoff, Guiliana; Sarnak, Peter; Valette, Alain (2003), Elementary number theory, group theory and Ramanjuan graphs, LMS student texts, 55, Cambridge University Press, ISBN 0-521-53143-8 
• Hoory, Shlomo; Linial, Nathan; Widgerson, Avi (2006), "Expander graphs and their applications", Bulletin (New series) of the American Mathematical Society 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8, http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf 
• Krebs, Mike; Shaheen, Anthony (2011), Expander families and Cayley graphs: A beginner's guide, Oxford University Press, ISBN 0-199-76711-4 

Research articles

• Ajtai, M.; Komlós, J.; Szemerédi, E. (1983), "An O(n log n) sorting network", Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 1–9, doi:10.1145/800061.808726 
• Ajtai, M.; Komlós, J.; Szemerédi, E. (1987), "Deterministic simulation in LOGSPACE", Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp. 132–140, doi:10.1145/28395.28410 
• Bobkov, S.; Houdré, C.; Tetali, P. (2000), "λ_∞, vertex isoperimetry and concentration", Combinatorica 20 (2): {153--172, doi:10.1007/s004930070018 }.
• Dinur, Irit (2007), "The PCP theorem by gap amplification", Journal of the ACM 54 (3): 12, doi:10.1145/1236457.1236459 .
• Gillman, D. (1998), "A Chernoff Bound for Random Walks on Expander Graphs", SIAM Journal on Computing (Society for Industrial and Applied Mathematics) 27 (4,): 1203–1220, doi:10.1137/S0097539794268765 
• Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291 

External links

• Brief introduction in Notices of the American Mathematical Society
• Introductory paper by Michael Nielsen
• Lecture notes from a course on expanders (by Nati Linial and Avi Wigderson)
• Lecture notes from yet another course on expanders (by Prahladh Harsha)
• Definition and application of spectral gap