Expander graphs II: Examples
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/.
Today’s post is a short post, giving some extremely useful explicit examples of expander graphs.
Explicit examples of expanders
We’ve seen previously that a family of -regular random graphs on vertices defines an expander. For applications it is often more useful to have more explicit constructions for expanders. In particular, for applications to algorithms it is often useful to construct expanders on vertices, where is some parameter describing problem size. Just to store a description of a random graph on so many vertices requires exponentially much time and space, and so is not feasible. Fortunately, more parsimonious constructions are possible, which we now describe.
Example: In this example the family of graphs is indexed by a prime number, . The set of vertices for the graph is just the set of points in , the field of integers modulo . We construct a -regular graph by connecting each vertex to and . The vertex is connected to and . According to the lecture notes by Linial and Wigderson, this was proved to be a family of expanders by Lubotsky, Phillips and Sarnak in 1988, but I don’t know a lower bound on the expansion parameter. Note that even for we can do basic operations with this graph (e.g., random walking along its vertices), using computational resources that are only polynomial in time and space. This makes this graph potentially far more useful in applications than the random graphs considered earlier.
Example: A similar but slightly more complex example is as follows. The vertex set is , where is some positive integer, and is the additive group of integers modulo . The degree is , and the vertex has edges to , and , where all addition is done modulo . Something which concerns me a little about this definition, but which I haven’t resolved, is what happens when is even and we choose so that, e.g., the vertices and coincide with one another. We would expect this duplication to have some effect on the expansion parameter, but I haven’t thought through exactly what.
Unfortunately, I don’t know any more examples of expanders, although I’m sure there are some! Still, hopefully you will agree that these examples are pretty nice: they are easy to describe, and allow us to work with expander graphs on exponentially large vertex sets, without expending too much effort. I haven’t proved that these families are expanders: doing that requires some extra technical tools based on the adjacency matrix of a graph, which is the subject of the next post.