Expander graph

In combinatorics, an expander graph is 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 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" (also "isoperimetric number") $h\left(G\right)$ of a graph $G$ is defined as: $h\left(G\right) = min_\left\{1 le |S|le frac\left\{n\right\}\left\{2\right\} \right\} frac$where $Gamma\left(S\right)$ stands for the set of vertices with at least one neighbor in $S$. In a variant of this definition (called "unique neighbor expansion")$Gamma\left(S\right)$ stands for the set of vertices in $V$ with "exactly" one neighbor in $S$.

pectral expansion

When $G$ is regular, a linear algebraic definition of expansion is possible based on the eigenvalues of the adjacency matrix $A=A\left(G\right)$ of $G$ (where $A_\left\{ii\right\}$ 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_\left\{n-1\right\}$. 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\left\{|lambda_1|,ldots, |lambda_\left\{n-1\right\}|\right\}$.

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 refers to the max of $left|lambda_1 ight|$ and $left|lambda_\left\{n-1\right\} ight|$. 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).

Expander families

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

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\left(G\right) ge g_\left\{1/2\right\}\left(G\right) - 1$. Consequently, every vertex expander family is also an edge expander family.

Similarly, when $G$ is $d$-regular, there is a relationship between $h\left(G\right)$ 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" [http://www.math.ias.edu/~boaz/ExpanderCourse/lecture02.ps] states that

: $frac\left\{1\right\}\left\{2\right\}\left(d - lambda_1\right) le h\left(G\right) le sqrt\left\{2d\left(d - lambda_1\right)\right\}$

As a result, a family $mathcal\left\{G\right\}$ of graphs is an edge expander family if and only if $mathcal\left\{G\right\}$ is a spectral expander family.

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 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 $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

The Chernoff bound states that, when sampling many independent samples from a random variables in the range $\left[-1, 1\right]$, 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.

References

*

* [http://www.ams.org/notices/200407/what-is.pdf Brief introduction in Notices of the American Mathematical Society]
* [http://www.qinfo.org/people/nielsen/blog/archive/notes/expander_graphs.pdf Introductory paper by Michael Nielsen]
* [http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf A thorough survey of the field by Hoory, Linial & Wigderson]
* [http://www.math.ias.edu/~boaz/ExpanderCourse/ Lecture notes from a course on expanders]
* [http://ttic.uchicago.edu/~prahladh/teaching/spring05/index.html Lecture notes from yet another course on expanders]
* [http://www.yann-ollivier.org/specgraph/specgraph.html Definition and application of spectral gap]

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Expander — can refer to:*Part of the process of audio level compression *Part of the process of signal compression *Part of the process of companding *MIDI processor, hardware or software, to synthesize sounds from MIDI commands *Turboexpander, a turbine… …   Wikipedia

• Expander mixing lemma — The expander mixing lemma states that, for any two subsets S, T of a regular expander graph G, 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. tatementLet G = (V, E) …   Wikipedia

• Expander walk sampling — The expander walk sampling theorem, the earliest version of which is due to Ajtai Komlós Szemerédi and the more general version typically attributed to Gillman, states that sampling from an expander graph is almost as good as sampling… …   Wikipedia

• Graph operations — Operations on graphs produce new graphs from old ones. They may be separated into the following major categories. Contents 1 Unary operations 1.1 Elementary operations 1.2 Advanced operations 2 …   Wikipedia

• Cheeger constant (graph theory) — In mathematics, the Cheeger constant (also Cheeger number or isoperimetric number) of a graph is a numerical measure of whether or not a graph has a bottleneck . The Cheeger constant as a measure of bottleneckedness is of great interest in many… …   Wikipedia

• Connectivity (graph theory) — In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) which need to be removed to disconnect the remaining nodes from each other[1]. It is… …   Wikipedia

• List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

• Cut (graph theory) — In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are… …   Wikipedia

• Isoperimetric inequality — The isoperimetric inequality is a geometric inequality involving the square of the circumference of a closed curve in the plane and the area of a plane region it encloses, as well as its various generalizations. Isoperimetric literally means… …   Wikipedia

• List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia