{"id":212,"date":"2005-05-26T08:34:10","date_gmt":"2005-05-25T22:34:10","guid":{"rendered":"http:\/\/michaelnielsen.org\/?p=212"},"modified":"2005-05-26T08:34:10","modified_gmt":"2005-05-25T22:34:10","slug":"expander-graphs-ii-examples","status":"publish","type":"post","link":"https:\/\/michaelnielsen.org\/blog\/expander-graphs-ii-examples\/","title":{"rendered":"Expander graphs II: Examples"},"content":{"rendered":"

Note:<\/strong> This post is one in a series introducing one of the deepest ideas in modern computer science, expander graphs<\/em>. 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\/<\/a>.<\/p>\n

Today’s post<\/strong> is a short post, giving some extremely useful explicit examples of expander graphs.<\/p>\n

Explicit examples of expanders<\/h3>\n

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.<\/p>\n

Example:<\/strong> 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.<\/p>\n

Example:<\/strong> 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.<\/p>\n

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<\/em> of a graph, which is the subject of the next post. <\/p>\n","protected":false},"excerpt":{"rendered":"

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… Continue reading Expander graphs II: Examples<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-212","post","type-post","status-publish","format-standard","hentry","category-3","entry"],"_links":{"self":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/212","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/comments?post=212"}],"version-history":[{"count":0,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/212\/revisions"}],"wp:attachment":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/media?parent=212"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/categories?post=212"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/tags?post=212"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}