Expander graphs – Network theory | Tangente

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

A graph can 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 network is known explicitly and in full), 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 involved will be assumed to be undirected.

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

The history of expander graphs is entirely modern, beginning in the late 1960s. It provides 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 may still emerge that are elementary and accessible to a broad audience.

Intuitively, an expander graph combines two seemingly contradictory properties: on the one hand, one can navigate it very efficiently to connect any two vertices, even if many of its edges were suddenly to disappear; on the other, the network's "cost" is not excessive—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, a certain positive constant h(G), called the Cheeger number of G, can be associated with a graph G (see sidebar). If h(G) > 0, the graph is connected: it is always possible to connect any pair of vertices by following edges of the graph. But the larger h(G) is, the more "robust" the graph becomes: for example, if h(G) is at least 1/10, two similarly sized parts of the graph can still be connected even after one edge in ten has been removed!

The existence of expander graphs means that, for arbitrarily large N, we can construct a graph with at least N vertices in which each vertex is connected to no more than a fixed "small" number of other vertices (six, for example), and whose Cheeger number is always at least 1/10 (or any other fixed positive value).

the number of edges greatly exceeds the number of vertices.

a single incident is enough to split the network into two disconnected parts.

For many years, the discovery of expander graphs—and, in particular, the proof that these objects exist—was credited 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 complete a particular construction, and proved that a randomly chosen sequence of ever larger graphs, with each vertex always having at most four neighbors, forms an expander family. 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. What is more, this application is particularly elegant.

But the story does not end there. Both Barzdin and Kolmogorov and Pinsker proved that expander graphs exist… without providing any concrete examples. They merely asserted that a graph put together at random has a good chance of being an expander. Although perfectly acceptable for proving that certain objects exist, this kind of random construction can pose two types of problem.

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

Furthermore, it is also natural to ask whether a random construction can be replaced with 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 to deep concepts in algebra and geometry. Many other constructions have since been discovered, but the existence of expander graphs still retains an air of mystery.

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, while the second, involving 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 collected works:

More precisely, Barzdin and Kolmogorov considered a finite graph with N vertices, each having, 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 the vertices and edges are assumed to be represented "physically" by balls or tubes with a radius of 1 cm, the question then becomes:

What is the smallest value of R > 0 such that 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 in a cube with side length approximately N^1/2;

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

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

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

Their second result, however, would be of no interest whatsoever if expander graphs did not exist! The two Russian mathematicians therefore went on to prove the existence of such graphs, to show that their statement was not vacuous. 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.

Each vertex is connected to a few other vertices chosen at random.

The second application of expander graphs is particularly elegant, partly because the final result makes no mention of graphs at all! It concerns a question posed by Gromov in the 1980s about a geometric way of measuring the complexity of knots. Consider such a knot in space. Gromov defines the knot's distortion as the maximum ratio A/B, where A is the distance between two points on the knot measured by following the knot itself, and B is the distance "as the crow flies" between the two points.

Now move the knot freely through space, even allowing it to stretch arbitrarily. Each position has an associated distortion, and the knot's intrinsic distortion is the smallest possible distortion across all the positions the knot can take. A knot with high distortion is extraordinarily complicated: however 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 with arbitrarily high distortion exist?

Using the expansion properties of certain special graphs, Gromov and Guth were able to answer 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 way to compute h(G), but it is extraordinarily inefficient: as it stands, it requires roughly 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 allows us at least to estimate the Cheeger constant h(G). Many open questions remain, however, in this rapidly… expanding field.