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 [tex]d[/tex]-regular random graphs on [tex]n[/tex] 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 [tex]O(2^n)[/tex] vertices, where [tex]n[/tex] 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, [tex]p[/tex]. The set of vertices for the graph [tex]G_p[/tex] is just the set of points in [tex]Z_p[/tex], the field of integers modulo [tex]p[/tex]. We construct a [tex]3[/tex]-regular graph by connecting each vertex [tex]x \neq 0[/tex] to [tex]x-1,x+1[/tex] and [tex]x^{-1}[/tex]. The vertex [tex]x=0[/tex] is connected to [tex]p-1,0[/tex] and [tex]1[/tex]. 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 [tex]p = O(2^n)[/tex] 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 [tex]Z_m \times Z_m[/tex], where [tex]m[/tex] is some positive integer, and [tex]Z_m[/tex] is the additive group of integers modulo [tex]m[/tex]. The degree is [tex]4[/tex], and the vertex [tex](x,y)[/tex] has edges to [tex](x\pm y,y)[/tex], and [tex](x,x \pm y)[/tex], where all addition is done modulo [tex]m[/tex]. Something which concerns me a little about this definition, but which I haven’t resolved, is what happens when [tex]m[/tex] is even and we choose [tex]y = m/2[/tex] so that, e.g., the vertices [tex](x+y,y)[/tex] and [tex](x-y,y)[/tex] 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.

1 comment

  1. expansion factors
    Example 2. for the Margulis graphs which are slightly different from Linial & Widgerson’s example the construction and estimation of exp. facto is given in [1]
    Set n = m^2 and V = Z_m \prod Z_m
    1 x, y -> x, y + 2x
    2 x, y -> x, y + 2x + 1
    3 x, y -> x, y + 2x + 2
    4 x, y -> x + 2y, y
    5 x, y -> x + 2y + 1, y
    6 x, y -> x + 2y + 2, y
    We got 12-regular graph G
    For G the second eighenvalue \lambda_1 \geq \frac {2 – \sqrt(3)}{3}
    So we can get expansion factor by Alon-Milman

    For example 1 it is not clear how to related to standard Lubotsky etal construction, I’ll try to get exp. factor after I finish some writting (a little bit busy now)

    Other examples of expanders from [1]
    A) The Paley graph P_p
    Let p be a prime congruent to 1 mod 4. P_p consist of p vertexes labelled by 0..p-1.
    Two vertiex are ajacent iff i-j is a non-zero quadratic residue modulo p.
    A very interesting results about this family of graphs (and their directed version) are presented in [2]. For example, these graphs are quasi random graphs” in sense of [2], Chapter 9.
    1 The second eigen-value is o(p)
    2 for every set of vertices S e(S) = \frac{1}{4}|S|^2 + o(p^2), where e(S) is the number of induced edges on S
    and so on
    B) The Paley sum graphs
    Let b be any prime number (not required to be congruent to 1 mod 4)

    C) The coset graphs
    Consider the finite field GF(p^t) and a coset x + GF(p) for x \in GF(p^t) \equiv GF(p)(x). The coset graph is constructed with vertices 1, \cdots, p^t – 1 = n and edges (a,b) if a + b is in the subset of integer corresponding to the coset x + GF(p)

    1 Fan R. K. Chung, “Spectral Graph Theory”, Chapter 6 “Expander and Explicit Contructions”
    2 Alon, Spencer, Probalistic method

Comments are closed.