Expander graph

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.[1]

Definitions

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.

Edge expansion

The edge expansion (also isoperimetric number or Cheeger constant) h(G) of a graph G on n vertices is defined as

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial S|}{|S|}},}$

where ${\displaystyle \partial S:=\{\{u,v\}\in E(G)\$ :\ u\in S,v\in V(G)\setminus S\}.}

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.[2]

Vertex expansion

The vertex isoperimetric number ${\displaystyle h_{\text{out}}(G)}$ (also vertex expansion or magnification) of a graph G is defined as

${\displaystyle h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},}$

where ${\displaystyle \partial _{\text{out}}(S)}$ is the outer boundary of S, i.e., the set of vertices in ${\displaystyle V(G)\setminus S}$ with at least one neighbor in S.[3] In a variant of this definition (called unique neighbor expansion) ${\displaystyle \partial _{\text{out}}(S)}$ is replaced by the set of vertices in V with exactly one neighbor in S.[4]

The vertex isoperimetric number ${\displaystyle h_{\text{in}}(G)}$ of a graph G is defined as

${\displaystyle h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}},}$

where ${\displaystyle \partial _{\text{in}}(S)}$ is the inner boundary of S, i.e., the set of vertices in S with at least one neighbor in ${\displaystyle V(G)\setminus S}$.[3]

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 ${\displaystyle A_{ij}}$ is the number of edges between vertices i and j.[5] Because A is symmetric, the spectral theorem implies that A has n real-valued eigenvalues ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$. It is known that all these eigenvalues are in [−d, d].

Because G is regular, the uniform distribution ${\displaystyle u\in \mathbb {R} ^{n}}$ with ${\displaystyle u_{i}=1/n}$ 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 λ₁ = d, where d is the degree of the vertices of G. The spectral gap of G is defined to be d − λ₂, and it measures the spectral expansion of the graph G.[6]

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 λ₂ is not enough, but indeed it is necessary to bound the absolute value of all the eigenvalues away from d:

${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}.}$

Since this is the largest eigenvalue corresponding to an eigenvector orthogonal to u, it can be equivalently defined using the Rayleigh quotient:

${\displaystyle \lambda =\max _{v\perp u,v\neq 0}{\frac {\|Av\|_{2}}{\|v\|_{2}}},}$

where

${\displaystyle \|v\|_{2}=\left(\sum _{i=1}^{n}v_{i}^{2}\right)^{1/2}}$

is the 2-norm of the vector ${\displaystyle v\in \mathbb {R} ^{n}}$.

The normalized versions of these definitions are also widely used and more convenient in stating some results. Here one considers the matrix ${\displaystyle {\tfrac {1}{d}}A}$, 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 A^TA.

Relationships between different expansion properties

The expansion parameters defined above are related to each other. In particular, for any d-regular graph G,

${\displaystyle h_{\text{out}}(G)\leq h(G)\leq d\cdot h_{\text{out}}(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 the isoperimetric constant h(G) and the gap d − λ₂ 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 λ₁=d and the first non-trivial eigenvalue is λ₂. If G is connected, then λ₂ < d. An inequality due to Dodziuk[7] and independently Alon and Milman[8] states that[9]

${\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}$

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:[10]

${\displaystyle h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1}$

${\displaystyle h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}.}$

Asymptotically speaking, the quantities ${\displaystyle {\frac {h^{2}}{d}}}$, ${\displaystyle h_{\text{out}}}$, and ${\displaystyle h_{\text{in}}^{2}}$ are all bounded above by the spectral gap ${\displaystyle O(d-\lambda _{2})}$.

Constructions

There are three general strategies for constructing families of expander graphs.[11] 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.[12]

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.[13] For every natural number n, one considers the graph G_n with the vertex set ${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$, where ${\displaystyle \mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} }$: For every vertex ${\displaystyle (x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$, its eight adjacent vertices are

${\displaystyle (x\pm 2y,y),(x\pm (2y+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).}$

Then the following holds:

Theorem. For all n, the graph G_n has second-largest eigenvalue ${\displaystyle \lambda (G)\leq 5{\sqrt {2}}}$.

Ramanujan graphs

By a theorem of Alon and Boppana, all sufficiently large d-regular graphs satisfy ${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1)}$, where ${\displaystyle \lambda _{2}}$ is the second largest eigenvalue in absolute value.[14] Ramanujan graphs are d-regular graphs for which this bound is tight, satisfying ${\displaystyle \lambda =\max _{|\lambda _{i}|<d}|\lambda _{i}|\leq 2{\sqrt {d-1}}}$.[15] Hence Ramanujan graphs have an asymptotically smallest possible value of ${\displaystyle \lambda _{2}}$. This makes them excellent spectral expanders.

Lubotzky, Phillips, and Sarnak (1988), Margulis (1988), and Morgenstern (1994) show how Ramanujan graphs can be constructed explicitly.[16] By a theorem of Friedman (2003), random d-regular graphs on n vertices are almost Ramanujan, that is, they satisfy

${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$

for every ${\displaystyle \varepsilon >0}$ with probability ${\displaystyle 1-o(1)}$ as n tends to infinity.[17]

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.

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 ${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}}$ 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 ${\displaystyle {\tfrac {d}{n}}\cdot |S|\cdot |T|}$ 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,

${\displaystyle E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S).}$

Then the expander mixing lemma says that the following inequality holds:

${\displaystyle \left|E(S,T)-{\frac {d\cdot |S|\cdot |T|}{n}}\right|\leq \lambda {\sqrt {|S|\cdot |T|}}.}$

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.

See also

• Algebraic connectivity
• Zig-zag product
• Superstrong approximation
• Spectral graph theory

Notes

1. Hoory, Linial & Wigderson (2006)
2. Definition 2.1 in Hoory, Linial & Wigderson (2006)
3. Bobkov, Houdré & Tetali (2000)
4. Alon & Capalbo (2002)
5. cf. Section 2.3 in Hoory, Linial & Wigderson (2006)
6. This definition of the spectral gap is from Section 2.3 in Hoory, Linial & Wigderson (2006)
7. Dodziuk 1984.
8. Alon & Spencer 2011.
9. Theorem 2.4 in Hoory, Linial & Wigderson (2006)
10. See Theorem 1 and p.156, l.1 in Bobkov, Houdré & Tetali (2000). Note that λ₂ there corresponds to 2(d − λ₂) of the current article (see p.153, l.5)
11. see, e.g., Yehudayoff (2012)
12. 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.
13. see, e.g., p.9 of Goldreich (2011)
14. Theorem 2.7 of Hoory, Linial & Wigderson (2006)
15. Definition 5.11 of Hoory, Linial & Wigderson (2006)
16. Theorem 5.12 of Hoory, Linial & Wigderson (2006)
17. Theorem 7.10 of Hoory, Linial & Wigderson (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 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 (New Series) of the American Mathematical Society, 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

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 978-0-89791-099-6
• 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
• 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
• 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" (PDF), Journal of the ACM, 54 (3): 12–es, CiteSeerX 10.1.1.103.2644, doi:10.1145/1236457.1236459.
• 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
• Yehudayoff, Amir (2012), "Proving expansion in three steps", ACM SIGACT News, 43 (3): 67–84, doi:10.1145/2421096.2421115

Recent Applications

• Hartnett, Kevin (2018), "Universal Method to Sort Complex Information Found", Quanta Magazine (published 13 August 2018)

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