Expander graphs

A graph is a fundamental concept in mathematics. Here we shall consider graphs consisting of finitely many vertices, each connected to other vertices by one or more edges. These edges may be directed.

A graph may represent, for example, a communication network (such as Zürich's tram network or the Paris Métro), an animal's neural network (such as the nervous system of the worm Caenorhabditis Elegans, the only animal whose entire network is explicitly known), or a family tree (see les Graphes, Bibliothèque Tangente 54, 2015).

For the questions and applications that interest us most, the edges of the graphs under consideration will be assumed to be undirected.

**

**

Expansion in graphs ======================================================================================================

Certain graphs, known as expanders, have such remarkable properties that their very existence seems paradoxical. More than one mathematician seems at first to have thought that they could not exist! Moreover, they have extraordinary applications in a wide variety of fields in mathematics and computer science (combinatorics, geometry, number theory, knot theory…).

The history of expander graphs is entirely modern, beginning in the late 1960s. It offers a striking demonstration of the unity of mathematics. Even today, at a time when research is increasingly specialized and often conceptually difficult, revolutionary new ideas can still emerge that are elementary and accessible to a wide audience.

Intuitively, an expander graph combines two seemingly contradictory properties: it allows any two vertices to be connected very efficiently, even if many of its edges suddenly disappear; yet the network's "cost" is not excessive—that is, the number of edges is relatively "small" compared with the number of vertices (so this is not simply a matter of connecting every vertex to every other one!). More precisely, every graph G has an associated positive constant h(G), called the Cheeger constant of G (see FOCUS). If h(G) > 0, the graph is connected: any pair of vertices can always be joined by following edges of the graph. The larger h(G), the more "robust" the graph is: for example, if h(G) is at least 1/10, any two similarly sized parts of the graph can still be connected even after one edge in ten has been removed!

To say that expander graphs exist means that, for every arbitrarily large number N, we know how to construct a graph with at least N vertices in which each vertex is connected to at most some fixed "small" number of other vertices (at most six, for example), while the Cheeger constant is always at least 1/10 (or any other fixed strictly positive value).

A turbulent history ==================================================================================================

For many years, the discovery of expander graphs—and, in particular, the proof that such objects exist—was attributed to Mark Semenovich Pinsker, in connection with a problem in theoretical computer science. In 1973, Pinsker introduced expander graphs as auxiliary objects that enabled him to carry through a particular construction, and proved that a randomly chosen sequence of increasingly large graphs, in which each vertex always has at most four neighbors, has the expander property. Much more recently, however, Larry Guth (re)discovered a fascinating paper by Yanis Barzdin and Andrei Kolmogorov, published in 1967, several years before Pinsker's. It contains not only a definition essentially equivalent to that of expander graphs (one difference being that Barzdin and Kolmogorov use directed graphs) and a proof of their existence, but also the first application of expander graphs outside combinatorics and theoretical computer science. Moreover, this application is particularly elegant.

=

The first constructions =================================================================================================

The story does not end there, however. Both Barzdin and Kolmogorov and Pinsker proved that expander graphs exist… without providing any concrete examples. They merely asserted that a graph constructed "without thinking" has a good chance of being an expander. Although perfectly acceptable for proving that certain objects exist, this kind of random construction can raise two kinds of problems.

First, in a particular practical application, one may not be free to choose the graphs one needs. Knowing that an expander graph exists is of little use if the task is to determine whether a particular graph has good expansion properties.

Moreover, it is natural to ask whether a random construction can be replaced by an explicit, deterministic one.

As early as 1973, Grigori Aleksandrovich Margulis succeeded in constructing explicit examples of expander graphs. To do so, he used an extremely elegant argument linking the expansion of certain graphs with deep concepts from algebra and geometry. Many other constructions have since been discovered, but the existence of expander graphs still retains an air of mystery.

A little geometry problem ==========================================================================================================

Among the many applications of expander graphs, two of the most beautiful are directly connected with Barzdin and Kolmogorov's original paper. The first was their motivation; the second, concerning a problem in knot theory, was discovered by Mikhail Gromov and Larry Guth.

Barzdin described the motivation as follows in the notes to Kolmogorov's works:

More precisely, Barzdin and Kolmogorov considered a finite graph with N vertices, each of which has (say) at most six neighbors. Such a graph can always be represented in space so that no two edges cross, except possibly at a shared vertex. If we represent the vertices and edges "physically" by balls or tubes with a radius of 1 cm, the question then becomes:

What is the smallest possible radius R > 0 for which the graph can be represented in space inside a cube of side length R?

Barzdin and Kolmogorov obtained two results:

– A graph can always be represented inside a cube of side length about N^1/2;

–If the graph is an expander (if its Cheeger constant is "sufficiently large"), then it cannot be represented inside a cube of side length less than (approximately) N^1/2.

Thus, in a sense, Barzdin and Kolmogorov proved that expander graphs are "as complicated as possible." Their proof is relatively elementary, once the exact definition of the Cheeger constant is known (see FOCUS).

Barzdin and Kolmogorov's first result was in fact already known to some "applied" computer scientists, who needed an efficient algorithm for physically representing a network in three-dimensional space.

The second result, meanwhile, would be of no interest whatsoever if expander graphs did not exist! To ensure that their statement was not vacuous, the two Russian mathematicians therefore went on to prove that such graphs exist. On the other hand, it is equally clear that there was no need here to construct them explicitly or to have explicit examples at hand.

The Gromov–Guth theorem ====================================================================================================

The second application of expander graphs is particularly elegant, partly because the statement of the final result makes no mention whatsoever of graphs! It concerns a question posed by Gromov in the 1980s about a geometric way of measuring the complexity of knots. Place such a knot in space. Gromov defines the knot's distortion as the greatest ratio A/B, where A is the distance between two points measured along the knot itself, and B is the straight-line distance between them.

Now move the knot freely through space, even allowing it to be stretched arbitrarily. Each position has an associated distortion, and the knot's intrinsic distortion is the smallest possible distortion over all the positions the knot can assume. If a knot has high distortion, it is extraordinarily complicated: no matter how it is arranged in space, some points that are "close" as the crow flies will in fact be very far apart along the knot.

As with expander graphs, the existence of such complicated knots is far from obvious. Gromov had asked:

Do knots of arbitrarily large distortion exist?

Using the expansion properties of certain special graphs, Gromov and Guth succeeded in answering the question in the affirmative.

Given an explicit graph G, one may wonder whether its Cheeger constant h(G) can be computed quickly, making it possible to check whether the graph has good expansion properties. The definition provides an obvious method for computing h(G), but an extraordinarily inefficient one: as it stands, it requires approximately 2^N operations, where N is the number of vertices of G. Fortunately, another constant associated with the graph is much easier to compute and can at least provide estimates of the Cheeger constant h(G). Many open questions nevertheless remain in this rapidly… expanding field.