Expander graphs I: Introduction

Note: This post is one in a series introducing one of the deepest ideas in modern computer science, expander graphs. Expanders are one of those powerful ideas that crop up in many apparently unrelated contexts, and that have a phenomenally wide range of uses. The goal of the posts is to explain what an expander is, and to learn just enough about them that we can start to understand some of their amazing uses. The posts require a little background in graph theory, computer science, linear algebra and Markov chains (all at about the level of a first course) to be comprehensible. I am not an expert on expanders, and the posts are just an introduction. They are are mostly based on some very nice 2003 lecture notes by Nati Linial and Avi Wigderson, available on the web at http://www.math.ias.edu/~boaz/ExpanderCourse/.

Introduction to expanders

Expander graphs are one of the deepest tools of theoretical computer science and discrete mathematics, popping up in all sorts of contexts since their introduction in the 1970s. Here’s a list of some of the things that expander graphs can be used to do. Don’t worry if not all the items on the list make sense: the main thing to take away is the sheer range of areas in which expanders can be applied.

• Reduce the need for randomness: That is, expanders can be used to reduce the number of random bits needed to make a probabilistic algorithm work with some desired probability.
• Find good error-correcting codes: Expanders can be used to construct error-correcting codes for protecting information against noise. Most astonishingly for information theorists, expanders can be used to find error-correcting codes which are efficiently encodable and decodable, with a non-zero rate of transmission. This is astonishing because finding codes with these properties was one of the holy grails of coding theory for decades after Shannon’s pioneering work on coding and information theory back in the 1940s.
• A new proof of PCP: One of the deepest results in computer science is the PCP theorem, which tells us that for all languages [tex]L[/tex] in NP there is a randomized polyonomial-time proof verifier which need only check a constant number of bits in a purported proof that [tex]x \in L[/tex] or [tex]x \not \in L[/tex], in order to determine (with high probability of success) whether the proof is correct or not. This result, originally established in the earlier 1990s, has recently been given a new proof based on expanders.

What’s remarkable is that none of the topics on this list appear to be related, a priori, to any of the other topics, nor do they appear to be related to graph theory. Expander graphs are one of these powerful unifying tools, surprisingly common in science, that can be used to gain insight into an an astonishing range of apparently disparate phenomena.

I’m not an expert on expanders. I’m writing these notes to help myself (and hopefully others) to understand a little bit about expanders and how they can be applied. I’m not learning about expanders with any specific intended application in mind, but rather because they seem to behind some of the deepest insights we’ve had in recent years into information and computation.

What is an expander graph? Informally, it’s a graph [tex]G = (V,E)[/tex] in which every subset [tex]S[/tex] of vertices expands quickly, in the sense that it is connected to many vertices in the set [tex]\overline S[/tex] of complementary vertices. Making this definition precise is the main goal of the remainder of this post.

Suppose [tex]G = (V,E)[/tex] has [tex]n[/tex] vertices. For a subset [tex]S[/tex] of [tex]V[/tex] we define the edge boundary of [tex]S[/tex], [tex]\partial S[/tex], to be the set of edges connecting [tex]S[/tex] to its complement, [tex]\overline S[/tex]. That is, [tex]\partial S[/tex] consists of all those edges [tex](v,w)[/tex] such that [tex]v \in S[/tex] and [tex]w \not \in S[/tex]. The expansion parameter for [tex]G[/tex] is defined by

[tex] h(G) \equiv \min_{S: |S| \leq n/2} \frac{|\partial S|}{|S|}, [/tex]

where [tex]|X |[/tex] denotes the size of a set [tex]X[/tex].

One standard condition to impose on expander graphs is that they be [tex]d[/tex]-regular graphs, for some constant [tex]d[/tex], i.e., they are graphs in which every vertex has the same degree, [tex]d[/tex]. I must admit that I’m not entirely sure why this [tex]d[/tex]-regularity condition is imposed. One possible reason is that doing this simplifies a remarkable result which we’ll discuss later, relating the expansion parameter [tex]h(G)[/tex] to the eigenvalues of the adjacency matrix of [tex]G[/tex]. (If you don’t know what the adjacency matrix is, we’ll give a definition later.)

Example: Suppose [tex]G[/tex] is the complete graph on [tex]n[/tex] vertices, i.e., the graph in which every vertex is connected to every other vertex. Then for any vertex in [tex]S[/tex], each vertex in [tex]S[/tex] is connected to all the vertices in [tex]\overline S[/tex], and thus [tex]|\partial S| = |S| \times |\overline S| = |S|(n-|S|)[/tex]. It follows that the expansion parameter is given by

[tex] h(G) = \min_{S: |S|\leq n/2} n-|S| = \left\lceil \frac{n}{2} \right\rceil. [/tex]

For reasons I don’t entirely understand, computer scientists are most interested in the case when the degree, [tex]d[/tex], is a small constant, like [tex]d = 2,3[/tex] or [tex]4[/tex], not [tex]d=n-1[/tex], as is the case for the complete graph. Here’s an example with constant degree.

Example: Suppose [tex]G[/tex] is an [tex]n \times n[/tex] square lattice in [tex]2[/tex] dimensions, with periodic boundary conditions (so as to make the graph [tex]4[/tex]-regular). Then if we consider a large connected subset of the vertices, [tex]S[/tex], it ought to be plausible that that the edge boundary set [tex]\partial S[/tex] contains roughly one edge for each vertex on the perimeter of the region [tex]S[/tex]. We expect there to be roughly [tex]\sqrt{|S|}[/tex] such vertices, since we are in two dimensions, and so [tex]|\partial S|/|S| \approx 1/\sqrt{|S|}[/tex]. Since the graph can contain regions [tex]S[/tex] with up to [tex]O(n^2)[/tex] vertices, we expect

[tex] h(G) = O\left( \frac{1}{n} \right) [/tex]

for this graph. I do not know the exact result, but am confident that this expression is correct, up to constant factors and higher-order corrections. It’d be a good exercise to figure out exactly what [tex]h(G)[/tex] is. Note that as the lattice size is increased, the expansion parameter decreases, tending toward [tex]0[/tex] as [tex]n\rightarrow \infty[/tex].

Example: Consider a random [tex]d[/tex]-regular graph, in which each of [tex]n[/tex] vertices is connected to [tex]d[/tex] other vertices, chosen at random. Let [tex]S[/tex] be a subset of at most [tex]n/2[/tex] vertices. Then a typical vertex in [tex]S[/tex] will be connected to roughly [tex]d \times |\overline S|/n[/tex] vertices in [tex]\overline S[/tex], and thus we expect [tex]|\partial S| \approx d \times |S| |\overline S|/n[/tex], and so

[tex] \frac{|\partial S|}{|S|} \approx d \frac{|\overline S|}{n}. [/tex]

Since [tex]|\overline S|[/tex] has its minimum at approximately [tex]n/2[/tex] it follows that [tex]h(G) \approx d/ 2[/tex], independent of the size [tex]n[/tex].

Exercise: Show that a disconnected graph always has expansion parameter [tex]0[/tex].

In each of our examples, we haven’t constructed just a single graph, but rather an entire family of graphs, indexed by some parameter [tex]n[/tex], with the property that as [tex]n[/tex] gets larger, so too does the number of vertices in the graph. Having access to an entire family in this way turns out to be much more useful than having just a single graph, a fact which motivates the definition of expander graphs, which we now give.

Suppose we have a family [tex]G_j = (V_j,E_j)[/tex] of [tex]d[/tex]-regular graphs, indexed by [tex]j[/tex], and such that [tex]|V_j| = n_j[/tex] for some increasing function [tex]n_j[/tex]. Then we say that the family [tex]\{ G_j \}[/tex] is a family of expander graphs if the expansion parameter is bounded strictly away from [tex]0[/tex], i.e., there is some small constant [tex]c[/tex] such that [tex]h(G_j) \geq c > 0[/tex] for all [tex]G_j[/tex] in the family. We’ll often abuse nomenclature slightly, and just refer to the expander [tex]\{ G_j \}[/tex], or even just [tex]G[/tex], omitting explicit mention of the entire family of graphs.

In this post we’ve defined expanders, said a little about what they’re useful for, and given an example – [tex]d[/tex]-regular random graphs – of an expander. In the next post, I’ll describe some more explicit and much more useful examples of expander graphs.