III.24 Expanders
Avi Wigderson
1 The Basic Definition
An expander is a special sort of GRAPH [III.34] that has remarkable properties and many applications. Roughly speaking, it is a graph that is very hard to disconnect because every set of vertices in the graph is joined by many edges to its complement. More precisely, we say that a graph with n vertices is a c-expander if for every m ≤ 
n and every set S of m vertices there are at least cm edges between S and the complement of S.
This definition is particularly interesting when G is sparse: in other words, when G has few edges. We shall concentrate on the important special case where G is regular of degree d for some fixed constant d that is independent of the number n of vertices: this means that every vertex is joined to exactly d others. When G is regular of degree d, the number of edges from S to its complement is obviously at most dm, so if c is some fixed constant (that is, not tending to zero with n), then the number of edges between any set of vertices and its complement is within a constant of the largest number possible. As this comment suggests, we are usually interested not in single graphs but in infinite families of graphs: we say that an infinite family of d-regular graphs is a family of expanders if there is a constant c > 0 such that each graph in the family is a c-expander.
2 The Existence of Expanders
The first person to prove that expanders exist was Pinkser, who proved that if n is large and d ≥ 3, then almost every d-regular graph with n vertices is an expander. That is, he proved that there is a constant c > 0 such that for every fixed d ≥ 3, the proportion of d-regular graphs with n vertices that are not expanders tends to zero as n tends to infinity. This proof was an early example of the PROBABILISTIC METHOD [IV.19 §3] in combinatorics. It is not hard to see that if a d-regular graph is chosen uniformly at random, then the expected number of edges leaving a set S is d|S|(n - |S|)/n, which is at least (d)|S|. Standard “tail estimates” are then used to prove that, for any fixed S, the probability that the number of edges leaving S is significantly different from its expected value is extremely small: so small that if we add up the probabilities for all sets, then even the sum is small. So with high probability all sets S have at least c|S| edges to their complement. (In one respect this description is misleading: it is not a straightforward matter to discuss probabilities of events concerning random d-regular graphs because the edges are not independently chosen. However, Bollobás has defined an equivalent model for random regular graphs that allows them to be handled.)
Note that this proof does not give us an explicit description of any expander: it merely proves that they exist in abundance. This is a drawback to the proof, because, as we shall see later, there are applications for expanders that depend on some kind of explicit description, or at least on an efficient method of producing expanders. But what exactly is an “explicit description” or an “efficient method”? There are many possible answers to this question, of which we shall discuss two. The first is to demand that there is an algorithm that can list, for any integer n, all the vertices and edges of a d-regular c-expander with around n vertices (we could be flexible about this and ask for the number of vertices to be between n and n2, say) in a time that is polynomial in n. (See COMPUTATIONAL COMPLEXITY [IV.20 §2] for a discussion of polynomial-time algorithms.) Descriptions of this kind are sometimes called “mildly explicit.”
To get an idea of what is “mild” about this, consider the following graph. Its vertices are all 01 sequences of length k, and two such sequences are joined by an edge if they differ in exactly one place. This graph is sometimes called the discrete cube in k dimensions. It has 2k vertices, so the time taken to list all the vertices and edges will be huge compared with k. However, for many purposes we do not actually need such a list: what matters is that there is a concise way of representing each vertex, and an efficient algorithm for listing the (representations of the) neighbors of any given vertex. Here the 01 sequence itself is a very concise representation, and given such a sequence σ it is very easy to list, in a time that is polynomial in k rather than 2k, the k sequences that can be obtained by altering σ in one place. Graphs that can be efficiently described in this way (so that listing the neighbors of a vertex takes a time that is polynomial in the logarithm of the number of vertices) are called strongly explicit.
The quest for explicitly constructed expanders has been the source of some beautiful mathematics, which has often used ideas from fields such as number theory and algebra. The first explicit expander was discovered by Margulis. We give his construction and another one; we stress that although these constructions are very simple to describe, it is rather less easy to prove that they really are expanders.
Margulis’s construction gives an 8-regular graph Gm for every integer m. The vertex set is 
m × m, where m is the set of all integers mod m. The neighbors of the vertex (x,y) are (x + y, y), (x - y, y), (x,y + x), (x,y-x), (x + y + 1,y),(x - y + 1, y), (x,y+x+ 1), (x, y - x + 1) (all operations are mod m). Margulis’s proof that Gm is an expander was based on REPRESENTATION THEORY [IV.9] and did not provide any specific bound on the expansion constant c. Gabber and Galil later derived such a bound using HARMONIC ANALYSIS [IV.11]. Note that this family of graphs is strongly explicit.
Another construction provides, for each prime p, a 3-regular graph with p vertices. This time the vertex set is p, and a vertex x is connected to x + 1, x - 1, and x-1 (where this is the inverse of x mod p, and we define the inverse of 0 to be 0). The proof that these graphs are expanders depends on a deep result in number theory, called the Selberg 3/16 theorem. This family is only mildly explicit, since we are at present unable to generate large primes deterministically.
Until recently, the only known methods for explicitly constructing expanders were algebraic. However, in 2002 Reingold, Vadhan, and Wigderson introduced the so-called zigzag product of graphs, and used it to give a combinatorial, iterative construction of expanders.
3 Expanders and Eigenvalues
The condition that a graph should be a c-expander involves all subsets of the vertices. Since there are exponentially many subsets, it would seem on the face of it that checking whether a graph is a c-expander is an exponentially long task. And, indeed, this problem turns Out to be CO-NP COMPLETE [IV.20 §§3, 4]. However, we shall now describe a closely related property that can be checked in polynomial time, and which is in some ways more natural.
Given a graph G with n vertices, its adjacency matrix A is the n × n matrix where Auv is defined to be 1 if u is joined to v and 0 otherwise. This matrix is real and symmetric, and therefore has n real EIGENVALUES [I.3 §4.3] λ1, λ2, . . . , λn, which we name in such a way that λ1 ≥ λ2 ≥. . . ≥ λn. Moreover, EIGENVECTORS [I.3 §4.3] with distinct eigenvalues are orthogonal.
It turns out that these eigenvalues encode a great deal of useful information about G. But before we come to this, let us briefly consider how A acts as a linear map. If we are given a function f, defined on the vertices of G, then Af is the function whose value at u is the sum of f(v) over all neighbors v of u. From this we see immediately that if G is d-regular and f is the function that is 1 at every vertex, then Af is the function that is d at every vertex. In other words, a constant function is an eigenvector of A with eigenvalue d. It is also not hard to see that this is the largest possible eigenvalue λ1, and that if the graph is connected, then the second largest eigenvalue λ2 will be strictly less than d.
In fact, the relationship between λ2 and connectivity properties of the graph is considerably deeper than this: roughly speaking, the further away λ2 is from d, the bigger the expansion parameter c of the graph. More precisely, it can be shown that c lies between (d - λ2) and 
. From this it follows that an infinite family of d-regular graphs is a family of expanders if and only if there is some constant a > 0 such that the spectral gaps d - λ2 are at least a for every graph in the family. One of the many reasons these bounds on c are important is that although, as we have remarked, it is hard to test whether a graph is a c-expander, its second largest eigenvalue can be computed in polynomial time. So we can at least obtain estimates for how good the expansion properties of a graph are.
Another important parameter of a d-regular graph G is the largest absolute value of any eigenvalue apart from λ1; this parameter is denoted by λ(G). If λ(G) is small, then G behaves in many respects like a random d-regular graph. For example, let A and B be two disjoint sets of vertices. If G were random, a small calculation shows that we would expect the number E(A, B) of edges from A to B to be about d|A| |B|/n. It can be shown that, for any two disjoint sets in any d-regular graph G, E(A, B) will differ from this expected amount by at most λ(G) 
. Therefore, if λ(G) is a small fraction of d, then between any two reasonably large sets A and B we get roughly the number of edges that we expect. This shows that graphs for which λ(G) is small “behave like random graphs.”
It is natural to ask how small λ(G) can be in d- regular graphs. Alon and Boppana proved that it was always at least 2
- g(n) for a certain function g that tends to zero as n increases. Friedman proved that almost all d-regular graphs G with n vertices have λ(G) ≤ 2 + h(n), where h(n) tends to zero, so a typical d-regular graph comes very close to matching the best possible bound for λ(G). The proof was a tour de force. Even more remarkably, it is possible to match the lower bound with explicit constructions: the famous Ramanujan graphs of Lubotzky, Philips, and Sarnak, and, independently, Margulis. They constructed, for each d such that d - 1 is a prime power, a family of d-regular graphs G with λ(G) = 2.
4 Applications of Expanders
Perhaps the most obvious use for expanders is in communication networks. The fact that expanders are highly connected means that such a network is highly “fault tolerant,” in the sense that one cannot cut off part of the network without destroying a large number of individual communication lines. Further desirable properties of such a network, such as a small diameter, follow from an analysis of random walks on expanders.
A random walk of length m on a d-regular graph G is a path v0, v1, . . . , vm, where each vi is a randomly chosen neighbor of vi-1. Random walks on graphs can be used to model many phenomena, and one of the questions one frequently asks about a random walk is how rapidly it “mixes.” That is, how large does m have to be before the probability that Vm = v is approximately the same for all vertices v?
If we let pk(v) be the probability that vk = v, then it is not hard to show that pk+1 = d-1 Apk. In other words, the transition matrix T of the random walk, which tells you how the distribution after k + 1 steps depends on the distribution after k steps, is d-1 times the adjacency matrix A. Therefore, its largest eigenvalue is 1, and if λ(G) is small then all other eigenvalues are small.
Suppose that this is the case, and let p be any PROBABILITY DISTRIBUTION [III.71] on the vertices of G. Then we can write p as a linear combination ∑i ui, where ui is an eigenvector of T with eigennlue d-1λi. If T is applied k times, then the new distribution will be ∑i(d-1λi)kui. If λ(G) is small, then(d-1λi)k tends rapidly to zero, except that it equals 1 when i = 1. In other words, after a short time, the “nonconstant part” of p goes to zero and we are left with the uniform distribution.
Thus, random walks on expanders mix rapidly. This property is at the heart of some of the applications of expanders. For example, suppose that V is a large set, f is a function from V to the interval [0,1], and we wish to estimate quickly and accurately the average of f. A natural idea is to choose a random sample v1, v2, . . . , vk of points in V and calculate the average k-1 
f (vi). If k is large and the vi are chosen independently, then it is not too hard to prove that this sample average will almost certainly be close to the true average: the probability that they differ by more than ∈ is at most e-e2k.
This idea is very simple, but actually implementing it requires a source of randomness. In theoretical computer science, randomness is regarded as a resource, and it is desirable to use less of it if one can. The above procedure needed about log(|V|) bits of randomness for each vi, so k log(|V|) bits in all. Can we do better? Ajtai, komlós, and Szemerédi showed that the answer is yes: big time! What one does is associate V with the vertices of an explicit expander. Then, instead of choosing v1, v2, . . . ,vk independently, one chooses them to be the vertices of a random walk in this expanding graph, starting at a random point v1 of V. The randomness needed for this is far smaller: log (|V|) bits for v1 and log(d) bits for each further vi, making log(|V|) + k log(d) bits in all. Since V is very large and d is a fixed constant, this is a big saving: we essentially pay only for the first sample point.
But is this sample any good? Clearly there is a heavy dependence between the vi. However, it can be shown that nothing is lost in accuracy: again, the probability that the estimate differs from the true mean by more than ∈ is at most e-e2k. Thus, there are no costs attached to the big saving in randomness.
This is just one of a huge number of applications of expanders, which include both practical applications and applications in pure mathematics. For instance, they were used by Gromov to give counterexamples to certain variants of the famous BAUM-CONNES CONJECTURE [IV.15 §4.4]. And certain bipartite graphs called “lossless expanders” have been used to produce linear codes with efficient decodings. (See RELIABLE TRANSMISSION OF INFORMATION [VII.6] for a description of what this means.)