In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. 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.
Intuitively, an expander graph 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.
The edge expansion (also isoperimetric number or Cheeger constant) h(G) of a graph G on n vertices is defined as
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.
The vertex isoperimetric number (also vertex expansion or magnification) of a graph G is defined as
where is the outer boundary of S, i.e., the set of vertices in with at least one neighbor in S. In a variant of this definition (called unique neighbor expansion) is replaced by the set of vertices in V with exactly one neighbor in S.
The vertex isoperimetric number of a graph G is defined as
where is the inner boundary of S, i.e., the set of vertices in S with at least one neighbor in .
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 is the number of edges between vertices i and j. Because A is symmetric, the spectral theorem implies that A has n real-valued eigenvalues . It is known that all these eigenvalues are in [−d, d] and more specifically, it is known that λn = −d if and only if G is bipartite.
More formally, we refer to an -vertex, -regular graph with as an -graph. The bound given by an -graph on for is useful many contexts, including the expander mixing lemma.
Because G is regular, the uniform distribution with for all i = 1, ..., n is the stationary distribution of G. That is, we have Au = du, and u is an eigenvector of A with eigenvalue λ1 = d, where d is the degree of the vertices of G. The spectral gap of G is defined to be d − λ2, and it measures the spectral expansion of the graph G.
If we set , as this is the largest eigenvalue corresponding to an eigenvector orthogonal to u, it can be equivalently defined using the Rayleigh quotient:
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 G. Its eigenvalues are between −1 and 1. 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 A, which are equal to the roots of the eigenvalues of the symmetric matrix ATA.
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.
When G is -regular, meaning each vertex is of degree , there is a relationship between the isoperimetric constant h(G) and the gap d − λ2 in the spectrum of the adjacency operator of G. By standard spectral graph theory, the trivial eigenvalue of the adjacency operator of a d-regular graph is λ1=d and the first non-trivial eigenvalue is λ2. If G is connected, then λ2 < d. An inequality due to Dodziuk and independently Alon and Milman states that
In fact, this inequality is tight. The lower bound is achieved for the hypercube , where and , while the upper bound is achieved for a cycle, where and . 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 , , and are all bounded above by the spectral gap .
There are three general strategies for explicitly 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 graph products. Noga Alon showed that certain graphs constructed from finite geometries are the sparsest examples of highly expanding graphs.
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 , where : For every vertex , its eight adjacent vertices are
Then the following holds:
Theorem. For all n, the graph Gn has second-largest eigenvalue .
By a theorem of Alon and Boppana, all sufficiently large d-regular graphs satisfy , where is the second largest eigenvalue in absolute value. As a direct consequence, we know that for every fixed and , there are only finitely many -graphs. Ramanujan graphs are d-regular graphs for which this bound is tight, satisfying . Hence Ramanujan graphs have an asymptotically smallest possible value of . This makes them excellent spectral expanders.
In 1985, Alon, conjectured that most -regular graphs on n vertices, for sufficiently large , are almost Ramanujan. That is, for , they satisfy
Reingold, Vadham, and Wigderson introduced the zig-zag product in 2003. Roughly speaking, the zig-zag product of two expander graphs produces a graph with only slightly worse expansion. Therefore, a zig-zag product can also be used to construct families of expander graphs. If is a -graph and is an -graph, then the zig-zag product is a -graph where has the following properties.
- If and , then ;
Note that property (1) implies that the zig-zag product of two expander graphs is also an expander graph, thus zig-zag products can be used inductively to create a family of expander graphs.
Intuitively, the construction of the zig-zag product can be thought of in the following way. Each vertex of is blown up to a "cloud" of m vertices, each associated to a different edge connected to the vertex. Each vertex is now labeled as where refers to an original vertex of and refers to the th edge of . Two vertices, and are connected if it is possible to get from to through the following sequence of moves.
- Zig - Move from to , using an edge of .
- Jump across clouds using edge in to get to
- Zag - Move from to using an edge of .
There are many results that show the existence of graphs with good expansion properties through probabilistic arguments. Pinsker showed that for a randomly chosen vertex left regular bipartite graph, for all subsets of vertices with high probability, where is a constant depending on that is . Alon and Roichman  showed that for every group of order and every , there is some such that the Cayley graph on with generators is an expander, i.e. has second eigenvalue less than , with high 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 the 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.
In a 2006 survey of expander graphs, Hoory, Linial, and Wigderson split the study of expander graphs into four categories: extremal problems, typical behavior, explicit constructions, and algorithms. Extremal problems focus on the bounding of expansion parameters, while typical behavior problems characterize how the expansion parameters are distributed over random graphs. Explicit constructions focus on constructing graphs that optimize certain parameters and algorithmic questions study the evaluation and estimation of parameters.
Expander mixing lemma
The expander mixing lemma states that for an -graph, 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 is. In a random d-regular graph, as well as in an Erdős–Rényi random graph with edge probability d/n, we expect edges between S and T.
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:
Many properties of -graphs are corollaries of the expander mixing lemmas, including the following.
- An independent set of a graph is a subset of vertices with no two vertices adjacent. In an -graph, an independent set has size at most .
- The chromatic number of a graph , , is the minimum number of colors needed such that adjacent vertices have different colors. Hoffman showed that , while Alon, Krivelevich, and Sudakov showed that if , then .
- The diameter of a graph is the maximum distance between two vertices, where the distance between two vertices is defined to be the shortest path between them. Chung showed that the diameter of an -graph is at most .
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.
AKS Sorting Network and Approximate Halvers
Bounded depth -halvers are a key part of the AKS sorting network and are constructed using expander graphs. An -halver takes as input a length permutation of and halves the inputs into two disjoint sets and such that for each integer at most at most of the smallest inputs are in and at most of the largest inputs are in . The sets of inputs and are an -halving.
Following Ajtai, Komlós & Szemerédi (1983), a depth -halver can be constructed as follows. Take an vertex, degree bipartite expander with parts and of equal size such that every subset of vertices of size at most has at least neighbors. The vertices of the graph can be thought of as registers that contain inputs and the edges can be thought of as wires that compare the inputs of two registers. At the start, arbitrarily place half of the inputs in and half of the inputs in and decompose the edges into perfect matchings. The goal is to end with roughly containing the smaller half of the inputs and containing roughly the larger half of the inputs. To achieve this, sequentially process each matching by comparing the registers paired up by the edges of this matching and correct any inputs that are out of order. Specifically, for each edge of the matching, if the larger input is in the register in and the smaller input is in the register in , then swap the two inputs so that the smaller one is in and the larger one is in . After all rounds, take to be the set of inputs in registers in and to be the set of inputs in registers in to obtain an -halving. To see this, notice that if a register in and in are connected by an edge then after the matching with this edge is processed, the input in is less than that of . Furthermore, this property remains true throughout the rest of the process. Now, suppose for some that more than of the inputs are in . Then by expansion properties of the graph, the registers of these inputs in are connected with at least registers in . Altogether, this constitutes more than registers so there must be some register in connected to some register in such that the final input of is not in , while the final input of is. This violates the previous property however, and thus the output sets and must be an -halving.
- Hoory, Linial & Wigderson (2006)
- Definition 2.1 in Hoory, Linial & Wigderson (2006)
- Bobkov, Houdré & Tetali (2000)
- Alon & Capalbo (2002)
- cf. Section 2.3 in Hoory, Linial & Wigderson (2006)
- This definition of the spectral gap is from Section 2.3 in Hoory, Linial & Wigderson (2006)
- Dodziuk 1984.
- Alon & Spencer 2011.
- Theorem 2.4 in Hoory, Linial & Wigderson (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)
- see, e.g., Yehudayoff (2012)
- Alon, Noga (1986). "Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory". Combinatorica. 6 (3): 207–219. CiteSeerX 10.1.1.300.5945. doi:10.1007/BF02579382. S2CID 8666466.
- see, e.g., p.9 of Goldreich (2011)
- Theorem 2.7 of Hoory, Linial & Wigderson (2006)
- Definition 5.11 of Hoory, Linial & Wigderson (2006)
- Theorem 5.12 of Hoory, Linial & Wigderson (2006)
- Alon, Noga (1986-06-01). "Eigenvalues and expanders". Combinatorica. 6 (2): 83–96. doi:10.1007/BF02579166. ISSN 1439-6912. S2CID 41083612.
- Friedman, Joel (2004-05-05). "A proof of Alon's second eigenvalue conjecture and related problems". arXiv:cs/0405020.
- Theorem 7.10 of Hoory, Linial & Wigderson (2006)
- Reingold, O.; Vadhan, S.; Wigderson, A. (2000). "Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors". Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc: 3–13. doi:10.1109/sfcs.2000.892006. ISBN 0-7695-0850-2. S2CID 420651.
- Pinkser, M. (1973). "On the Complexity of a Concentrator". SIAM Journal of Computing. SIAM. CiteSeerX 10.1.1.393.1430.
- Alon, N.; Roichman, Y. (1994). "Random Cayley graphs and Expanders". Random Structures and Algorithms. Wiley Online Library. 5 (2): 271–284. doi:10.1002/rsa.3240050203.
- Hoffman, A. J.; Howes, Leonard (1970). "On Eigenvalues and Colorings of Graphs, Ii". Annals of the New York Academy of Sciences. 175 (1): 238–242. Bibcode:1970NYASA.175..238H. doi:10.1111/j.1749-6632.1970.tb56474.x. ISSN 1749-6632. S2CID 85243045.
- Alon, Noga; Krivelevich, Michael; Sudakov, Benny (1999-09-01). "Coloring Graphs with Sparse Neighborhoods". Journal of Combinatorial Theory, Series B. 77 (1): 73–82. doi:10.1006/jctb.1999.1910. ISSN 0095-8956.
- Chung, F. R. K. (1989). "Diameters and eigenvalues". Journal of the American Mathematical Society. 2 (2): 187–196. doi:10.1090/S0894-0347-1989-0965008-X. ISSN 0894-0347.
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 978-0-8218-0315-8
- Davidoff, Guiliana; Sarnak, Peter; Valette, Alain (2003), Elementary number theory, group theory and Ramanujan graphs, LMS student texts, 55, Cambridge University Press, ISBN 978-0-521-53143-6
- Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications" (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8
- Krebs, Mike; Shaheen, Anthony (2011), Expander families and Cayley graphs: A beginner's guide, Oxford University Press, ISBN 978-0-19-976711-3
- 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 978-0-89791-099-6, S2CID 15311122
- 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 978-0-89791-221-1, S2CID 15323404
- Alon, N.; Capalbo, M. (2002), "Explicit unique-neighbor expanders", The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings, p. 73, CiteSeerX 10.1.1.103.967, doi:10.1109/SFCS.2002.1181884, ISBN 978-0-7695-1822-0, S2CID 6364755
- Bobkov, S.; Houdré, C.; Tetali, P. (2000), "λ∞, vertex isoperimetry and concentration", Combinatorica, 20 (2): 153–172, doi:10.1007/s004930070018, S2CID 1173532.
- Dinur, Irit (2007), "The PCP theorem by gap amplification" (PDF), Journal of the ACM, 54 (3): 12–es, CiteSeerX 10.1.1.103.2644, doi:10.1145/1236457.1236459, S2CID 53244523.
- Dodziuk, Jozef (1984), "Difference equations, isoperimetric inequality and transience of certain random walks", Trans. Amer. Math. Soc., 284 (2): 787–794, doi:10.2307/1999107, JSTOR 1999107.
- Gillman, D. (1998), "A Chernoff Bound for Random Walks on Expander Graphs", SIAM Journal on Computing, 27 (4): 1203–1220, doi:10.1137/S0097539794268765
- Goldreich, Oded (2011), "Basic Facts about Expander Graphs" (PDF), Studies in Complexity and Cryptography, Lecture Notes in Computer Science, 6650: 451–464, CiteSeerX 10.1.1.231.1388, doi:10.1007/978-3-642-22670-0_30, ISBN 978-3-642-22669-4
- Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM, 55 (4): 1–24, doi:10.1145/1391289.1391291, S2CID 207168478
- Yehudayoff, Amir (2012), "Proving expansion in three steps", ACM SIGACT News, 43 (3): 67–84, doi:10.1145/2421096.2421115, S2CID 18098370
- Hartnett, Kevin (2018), "Universal Method to Sort Complex Information Found", Quanta Magazine (published 13 August 2018)