Expander graph
Encyclopedia : E : EX : EXP : Expander graph
In combinatorics, an expander graph refers to a sparse graph which has high connectivity properties, quantified using vertex or edge expansion as described below. Expander constructions have spawned research in pure and applied mathematics, with several applications to computer science, and in particular to theoretical computer science, 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 [h(G)] of a graph [G] is defined as- [h(G) = \min_ } \frac
>
>
] where the minimum is over all nonempty sets [S] of at most [n/2] vertices, and [\partial(S)] stands for the set of edges with exactly one endpoint in [S]. Vertex expansion
The [\alpha]-vertex expansion [g_\alpha(G)] of a graph [G] is defined as- [g_\alpha(G) = \min_} \frac
>
>
] where [\Gamma(S)] stands for the set of vertices with at least one neighbor in [S]. In a variant of this definition (called unique neighbor expansion) [\Gamma(S)] stands for the set of vertices in [V] with exactly one neighbor in [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_] is the number of loops at the [i]th vertex). Because [A] is symmetric, the Spectral theorem implies that [A] has [n] real-valued eigenvalues [\lambda_0 \ge \lambda_1 \ge \ldots \ge \lambda_]. Because [G] is regular, [\lambda_0=d] where [d] is the degree of regularity of [G]. In some contexts, the spectral gap of [G] is defined to be [d-\lambda_1]. In other contexts, the spectral gap refers to [d-\lambda], where [\lambda=\max\|\}].Expander families
A family [\mathcal = \] 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]. Similarly, [\mathcal] is a vertex expander family if there is a constant [c > 1] such that [g_(G) \ge c] for each [G \in \mathcal], and [\mathcal] is a spectral expander family if some positive constant is a lower bound for the spectral gap of each [G \in \mathcal].These definitions can be extended to the case of directed graphs. 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.
Relationship between the different definitions
The expansion parameters defined above are related to each other. In particular, for any graph [G], [h(G) \ge g_(G) - 1]. Consequently, every vertex expander family is also an edge expander family.Similarly, when [G] is [d]-regular, there is a relationship between [h(G)] and the spectral gap [d - \lambda_1] of [G]. An inequality due to "Cheeger and Buser in the continuous case and Tanner, Alon, and Milman in the discrete case" [link] states that
- [\frac(d - \lambda_1) \le h(G) \le \sqrt]
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 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
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, pseudorandomness generators, sorting networks and robust computer networks. They have also been used in proving many important results in computational complexity theory, such as SL=L and the PCP Theorem. In Cryptography too, expander graphs are used to construct hash functions.
External links
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.
- [g_\alpha(G) = \min_} \frac