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.
Contents
- Definitions
- Edge expansion
- Vertex expansion
- Spectral expansion
- Relationships between different expansion properties
- Cheeger inequalities
- Constructions
- Margulis Gabber Galil
- Ramanujan graphs
- Applications and useful properties
- Expander mixing lemma
- Expander walk sampling
- Expander property of the braingraphs
- References
Definitions
Intuitively, an expander is a finite, undirected multigraph in which every subset of the vertices that 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
where
In the equation, the minimum is over all nonempty sets S of at most n/2 vertices and ∂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
where
The vertex isoperimetric number
where
Spectral expansion
When G is d-regular, a linear algebraic definition of expansion is possible based on the eigenvalues of the adjacency matrix A = A(G) of G, where
Because G is regular, the uniform distribution
It is known that λn = −d if and only if G is bipartite. In many contexts, for example in the expander mixing lemma, a bound on λ2 is not enough, but indeed it is necessary to bound the absolute value of all the eigenvalues away from d:
Since this is the largest eigenvalue corresponding to an eigenvector orthogonal to u, it can be equivalently defined using the Rayleigh quotient:
where
is the 2-norm of the vector
The normalized versions of these definitions are also widely used and more convenient in stating some results. Here one considers the matrix
Relationships between different expansion properties
The expansion parameters defined above are related to each other. In particular, for any d-regular graph 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 − λ2 of G. An inequality due to Tanner and independently Alon and Milman states that
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:
Asymptotically speaking, the quantities
Constructions
There are three general strategies for constructing families of expander graphs. The first strategy is algebraic and group-theoretic, the second strategy is analytic and uses additive combinatorics, and the third strategy is combinatorial and uses the zig-zag and related graphs products. Noga Alon showed that certain graphs constructed from finite geometries are the sparsest examples of highly expanding graphs.
Margulis-Gabber-Galil
Algebraic constructions based on Cayley graphs are known for various variants of expander graphs. The following construction is due to Margulis and has been analysed by Gabber and Galil. For every natural number n, one considers the graph Gn with the vertex set
Then the following holds:
Theorem. For all n, the graph Gn has second-largest eigenvalue
Ramanujan graphs
By a theorem of Alon and Boppana, all large enough d-regular graphs satisfy
Lubotzky, Phillips, and Sarnak (1988), Margulis (1988), and Morgenstern (1994) show how Ramanujan graphs can be constructed explicitly. By a theorem of Friedman (2003), random d-regular graphs on n vertices are almost Ramanujan, that is, they satisfy
with probability
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
The expander mixing lemma states that, for any two subsets of the vertices S, T ⊆ V, the number of edges between S and T is approximately what you would expect in a random d-regular graph. The approximation is better the smaller
More formally, let E(S, T) denote the number of edges between S and T. If the two sets are not disjoint, edges in their intersection are counted twice, that is,
Then the expander mixing lemma says that the following inequality holds:
where λ is the absolute value of the normalized second largest eigenvalue.
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 many fewer random bits than sampling independently.
Expander property of the braingraphs
Using the magnetic resonance imaging (MRI) data of the NIH-funded large Human Connectome Project, it was shown by Szalkai et al that the graph, describing the anatomical brain connections between up to 1015 cerebral areas, is significantly better expander in women than in men.