Expander Graph Information
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.[1]
Contents |
Definitions
Intuitively, an expander is a finite, undirected multigraph in which every subset of the vertices "which 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) of a graph is defined as
where the minimum is over all nonempty sets of at most vertices and is the edge boundary of , i.e., the set of edges with exactly one endpoint in .[2]
Vertex expansion
The vertex isoperimetric number (also vertex expansion or magnification) of a graph is defined as
where is the outer boundary of , i.e., the set of vertices in with at least one neighbor in .[3] In a variant of this definition (called unique neighbor expansion) is replaced by the set of vertices in with exactly one neighbor in .[4]
The vertex isoperimetric number of a graph is defined as
where is the inner boundary of , i.e., the set of vertices in with at least one neighbor in .[3]
Spectral expansion
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 edges between vertices and .[5] Because is symmetric, the spectral theorem implies that has real-valued eigenvalues . It is known that all these eigenvalues are in .
Because is regular, the uniform distribution with for all is the stationary distribution of . That is, we have , and is an eigenvector of with eigenvalue , where is the degree of the vertices of . The spectral gap of is defined to be , and it measures the spectral expansion of the graph .[6]
It is known that if and only if is bipartite. In many context, for example in the expander mixing lemma, it is necessary to bound from below not only the gap between and , but also the gap between and the second-largest eigenvalue in absolute value: . Since this is the largest eigenvalue corresponding to an eigenvector orthogonal to , 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 , which is the Markov transition matrix of the graph . Its eigenvalues are between and . For not necessarily regular graphs, the spectrum of a graph can be defined similarly using the eigenvalues of the Laplacian matrix. For directed graphs, one considers the singular values of the adjacency matrix , which are equal to the roots of the eigenvalues of the symmetric matrix .
Relationships between different expansion properties
The expansion parameters defined above are related to each other. In particular, for any -regular graph ,
Consequently, for constant degree graphs, vertex and edge expansion are qualitatively the same.
Cheeger inequalities
When is -regular, there is a relationship between and the spectral gap of . An inequality due to Tanner and independently Alon and Milman[7] 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.
| This article may contain original research. Please improve it by verifying the claims made and adding references. Statements consisting only of original research may be removed. More details may be available on the talk page. (March 2012) |
Similar connections between vertex isoperimetric numbers and the spectral gap have also been studied:[9]
Asymptotically speaking, the quantities , , and are all bounded above by the spectral gap .
Examples of expanders
Petersen graph
The Petersen graphConsider the 3-regular graph G on 10 vertices (n = 10, d = 3) shown.
If we number the vertices by going around twice, starting with the outside pentagon and then the inside pentagon, G has the following adjacency matrix:
One can calculate that the two largest eigenvalues of this matrix are 3 and 1. From this, one may deduce that
and consequently that .
In fact, . To persuade oneself of this, it suffices to consider the five vertices in the central star: there are five edges that touch exactly one of these vertices, giving an edge expansion for this set of 5/5 = 1.
Ramanujan graphs
By a theorem of Alon and Boppana, all large enough -regular graphs satisfy .[10] Ramanujan graphs are -regular graphs that meet this bound, that is, they satisfy .[11] Hence Ramanujan graphs have an asymptotically smallest possible second-largest eigenvalue (in absolute value).
Lubotzky, Phillips, and Sarnak (1988), Margulis (1988), and Morgenstern (1994) show how Ramanujan graphs can be constructed explicitly.[12] By a theorem of Friedman (2003), random d-regular graphs on vertices are almost Ramanujan, that is, they satisfy with probability as tends to infinity.[13]
Other examples
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 lemmaThe 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. The approximation is better, the smaller is. In a random -regular graph, as well as in an Erdős–Rényi random graph with edge probability , we expect edges between and .
More formally, let denote the number of edges between and . 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:
Expander walk sampling
Main article: Expander walk samplingThe 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 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.
See also
Notes
- ^ Hoory, Linial & Widgerson (2006)
- ^ Definition 2.1 in Hoory, Linial & Widgerson (2006)
- ^ a b Bobkov, Houdré & Tetali (2000)
- ^ Alon & Capalbo (2002)
- ^ cf. Section 2.3 in Hoory, Linial & Widgerson (2006)
- ^ This definition of the spectral gap is from Section 2.3 in Hoory, Linial & Widgerson (2006)
- ^ Alon & Spencer 2011.
- ^ Theorem 2.4 in Hoory, Linial & Widgerson (2006)
- ^ See Theorem 1 and p.156, l.1 in Bobkov, Houdré & Tetali (2000). Note that λ2 there corresponds to 2(d − λ2) of the current article (see p.153, l.5)
- ^ Theorem 2.7 of Hoory, Linial & Widgerson (2006)
- ^ Definition 5.11 of Hoory, Linial & Widgerson (2006)
- ^ Theorem 5.12 of Hoory, Linial & Widgerson (2006)
- ^ Theorem 7.10 of Hoory, Linial & Widgerson (2006)
References
Textbooks and surveys
- Alon, N.; Spencer, Joel H. (2011). "9.2. Eigenvalues and Expanders". The Probabilistic Method (3rd ed.). John Wiley & Sons.
- 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-19-976711-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, ISBN 0-89791-099-0
- Ajtai, M.; Komlós, J.; Szemerédi, E. (1987), Deterministic simulation in LOGSPACE, "Proceedings of the 19th Annual ACM Symposium on Theory of Computing", ACM: pp. 132–140, DOI:10.1145/28395.28410, ISBN 0-89791-221-7
- Alon, N.; Capalbo, M. (2002). "Explicit unique-neighbor expanders". The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. pp. 73. DOI:10.1109/SFCS.2002.1181884. ISBN 0-7695-1822-2.
- 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 a course on expanders (by Prahladh Harsha)
- Definition and application of spectral gap
Categories:
|