where stands for the set of vertices with at least one neighbor in . In a variant of this definition (called unique neighbor expansion)
stands for the set of vertices in with exactly one neighbor in .
When is regular, a linear algebraic definition of expansion is possible based on the eigenvalues of the adjacency matrix of (where is the number of loops at the th vertex). Because is symmetric, the Spectral theorem implies that has real-valued eigenvalues . Because is regular, where is the degree of regularity of . In some contexts, the spectral gap of is defined to be . In other contexts, the spectral gap refers to , where .
The normalized version of this definition, where we consider the matrix 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 refers to the max of and . 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).
A family of -regular graphs is an edge expander family if there is a constant such that for each . Typically we want to be constant, though it is sometimes also interesting to consider or even . Similarly, is a vertex expander family if there is a constant such that for each , and is a spectral expander family if some positive constant is a lower bound for the spectral gap of each .
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 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 , . Consequently, every vertex expander family is also an edge expander family.
Similarly, when is -regular, there is a relationship between and the spectral gap of . An inequality due to "Cheeger and Buser in the continuous case and Tanner, Alon, and Milman in the discrete case" states that
As a result, a family of graphs is an edge expander family if and only if is a spectral expander family.
Examples of expanders
A random -regular graph has good expansion, with high probability. Ramanujan graphs are a family of -regular expander graphs with 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 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.
The following are some properties of expander graphs that have proven useful in many areas.
Expander mixing lemma
The expander mixing lemma states that, for any two subsets of the vertices , the number of edges between and is approximately what you would expect in a random -regular graph, i.e. .
Expander walk sampling
The Chernoff bound states that, when sampling many independent samples from a random variables in the range , with high probability the average of our samples is close to the expectation of the random variable. The expander walk sampling lemma, due to Gillman and Ajtai-Komlós-Szemerédi, 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.
HighBeam Research, Inc. © Copyright 2009.
Copyright © 2013 Dictionary.com, LLC. All rights reserved.