CS359G Lecture 16: Constructions of Expanders

In which we give an explicit construction of expander graphs of polylogarithmic degree, state the properties of the zig-zag product of graphs, and provide an explicit construction of a family of constant-degree expanders using the zig-zag product and the polylogarithmic-degree construction.

A family of expanders is a family of graphs , , such that each graph is -regular, and the edge-expansion of each graph is at least , for an absolute constant independent of . Ideally, we would like to have such a construction for each , although it is usually enough for most applications that, for some constant and every , there is an for which the construction applies in the interval , or even the interval . We would also like the degree to be slowly growing in and, ideally, to be bounded above by an explicit constant. Today we will see a simple construction in which and a more complicated one in which .

An explicit construction of a family of expanders is a construction in which is “efficiently computable” given . The weakest sense in which a construction is said to be explicit is when, given , the (adjacency matrix of the) graph can be constructed in time polynomial in . A stronger requirement, which is necessary for several applications, is that given and , the list of neighbors of the -th vertex of can be computed in time polynomial in .

In many explicit constructions of constant-degree expanders, the construction is extremely simple, and besides satisfying the stricter definition of “explicit” above, it is also such that the adjacency list of a vertex is given by a “closed-form formula.” The analysis of such constructions, however, usually requires very sophisticated mathematical tools.

Example 1 Let be a prime, and define the graph in which , and, for , the vertex is connected to , to and to its multiplicative inverse . The vertex is connected to , to , and has a self-loop. Counting self-loops, the graph is 3-regular: it is the union of a cycle over and of a matching over the vertices ; the vertices , , have a self-loop each. There is a constant such that, for each , the graph has edge expansion at least . Unfortunately, no elementary proof of this fact is known. The graph is shown in the picture below.

Constructions based on the zig-zag graph product, which we shall see next, are more complicated to describe, but much simpler to analyze.

We begin by describing a building block in the construction, which is also an independently interesting construction: a family of expanders with polylogarithmic degree, which have both a very simple description and a very simple analysis.

T-rex on conditional results

See also the mouse-over text on this strip.

CS261 Lecture 15: the LP of Max Flow

In which we look at the linear programming formulation of the maximum flow problem, construct its dual, and find a randomized-rounding proof of the max flow – min cut theorem.

In the first part of the course, we designed approximation algorithms “by hand,” following our combinatorial intuition about the problems. Then we looked at linear programming relaxations of the problems we worked on, and we saw that approximation algorithms for those problems could also be derived by rounding a linear programming solution. We also saw that our algorithms could be interpreted as constructing, at the same time, an integral primal solution and a feasible solution for the dual problem.

Now that we have developed exact combinatorial algorithms for a few problems (maximum flow, minimum s-t cut, global min cut, maximum matching and minimum vertex cover in bipartite graphs), we are going to look at linear programming relaxations of those problems, and use them to gain a deeper understanding of the problems and of our algorithms.

We start with the maximum flow and the minimum cut problems.

CS261 Lecture14: Algorithms in Bipartite Graphs

In which we show how to solve the maximum matching problem and the minimum vertex cover problem in bipartite graphs.

CS359G Lecture 14: ARV Rounding

In which we begin to discuss the Arora-Rao-Vazirani rounding procedure.

Recall that, in a graph with adjacency matrix , then ARV relaxation of the sparsest cut problem is the following semidefinite program.

If we denote by the optimum of the relaxation, then we claimed that

where the first inequality follows from the fact that is a relaxation of , and the second inequality is the result whose proof we begin to discuss today.

CS261 Lecture 13: Edge Connectivity

In which we describe a randomized algorithm for finding the minimum cut in an undirected graph.

Bad Signs

1. Justin Bieber’s dad is younger than me;
2. The New York Times writes that “While the younger generation is losing interest in blogging, people approaching middle age and older are sticking with it.”

CS261 Lecture 12: the Push-Relabel Algorithm

In which we prove that the basic implementation of the push-relabel algorithm runs in time .

CS261 Lecture 11: Strongly Polynomial Time Algorithms

In which we prove that the Edmonds-Karp algorithm for maximum flow is a strongly polynomial time algorithm, and we begin to talk about the push-relabel approach.

The keyboard that goes “CLICK”

When I got a computer for my new office at Stanford last year, it came with the Apple wireless keyboard, a piece of equipment that some people like very much, and that has a handsome and minimalist design. The bluetooth connection was, however, occasionally flaky, and it seemed silly to have a battery operated device sitting in front of a desktop. So I decided to buy a wired keyboard instead, and since everybody raves about how good it is to type on Lenovo laptops, I thought Lenovo would sell a keyboard made to feel like their laptops. Unfortunately there does not seem to be such a thing.

Searching for information about keyboards, however, I found a whole online cult devoted to the keyboards that IBM made for its PC in the 1980s: the IBM Model M keyboard. Although I never owned or used an IBM PC, I remember using similar keyboards when I was a graduate student in the mid 1990s, and we each had a terminal on our desk connected to a mainframe in the basement. The terminals had monochromatic, text-only, displays, but they keyboards were good, and, every time you would press a key, they would go *CLICK*, just like the 1980s IBM keyboards. (The terminals were made by HP and were 1980s technology.)

The license/patents to make these keyboards went to Lexmark, when IBM spun off its printers/devices business. Making the keyboards, however, was not profitable because they never break — see for example this video of a Model M versus a watermelon.

Lexmark then sold the license/patents to Unicomp, an American company whose business is to make clones of the IBM Model M keyboard and other 1980s models.

So that’s what I got for my office and, while I feel rather self-conscious about showing enthusiasm about a keyboard, it is awesome. (To be precise, the keyboard I got is not an exact clone of the IBM model M: mine has a USB cable, a “Windows” key, and it works with a Mac without drivers. The Windows key becomes the “command” key. For the purists, it is possible to buy actual IBM models M, with a PS/2 interface which can be connected to a USB via converter, at clickykeyboards.com, where they even have “mint condition never used” ones.)

This term, as readers of in theory might have noticed, I am writing notes for two classes, which means that I am typing for roughly 15-20 hours a week, mostly at home. Usually, at home I would work using the laptop on the sofa, and use my desk for storage, but this wasn’t good this term, so I (mostly) cleared the desk, got a monitor, a mouse, another, awesome Unicomp keyboard, and hooked it all up to my MacBook Air (which has new hinges, yay!).