Chapter 52. Expansion and Expanders

Expansion measures how quickly a set of vertices reaches the rest of the graph.

A graph may be sparse and still be highly connected. This is the central idea behind expander graphs. An expander has relatively few edges, but every small or medium-sized set of vertices has many edges or neighbors leaving it. In this sense, expanders behave like robust networks despite having bounded degree. Expander graphs are commonly described as sparse graphs with strong connectivity properties, measured through vertex, edge, or spectral expansion.

Expansion strengthens the ideas of cuts and connectivity. A graph can have no small cut vertices or bridges, but still contain a bottleneck separating two large regions. Expansion rules out such bottlenecks.

52.1 Boundary of a Vertex Set

Let

be an undirected graph, and let

The edge boundary of $S$, denoted

is the set of edges with exactly one endpoint in $S$:

This is the same object as the cut set

The outer vertex boundary of $S$, denoted

is the set of vertices outside $S$ that have at least one neighbor in $S$:

The edge boundary counts escaping edges. The vertex boundary counts new vertices reached from $S$.

Both notions measure how well $S$ is connected to the rest of the graph.

52.2 Edge Expansion

The edge expansion of a graph measures the smallest ratio between the number of edges leaving a set and the size of the set.

For a graph $G=(V,E)$ with

the edge expansion is often defined as

The restriction

prevents counting both sides of the same cut. Every cut has two sides, and we measure the smaller side.

If $h(G)$ is large, then every set of at most half the vertices has many edges leaving it. There is no poorly connected region that can be separated from the rest by a small number of edges. This definition is also called the isoperimetric number or Cheeger constant of the graph.

52.3 Vertex Expansion

Vertex expansion measures how many new vertices a set reaches.

The outer vertex expansion of $G$ is commonly defined as

If this number is large, then every small set has many outside neighbors.

Vertex expansion is especially useful when edges are less important than reachable vertices. For example, in communication or search problems, one may care less about how many links leave a region and more about how many new nodes can be reached.

Edge expansion and vertex expansion are related, but they are not identical. A set may have many outgoing edges that all lead to the same small group of outside vertices. In that case edge expansion may be high while vertex expansion is lower.

In bounded-degree graphs, the two notions are qualitatively close because no outside vertex can absorb arbitrarily many edges.

52.4 Expander Graphs

An expander graph is a sparse graph with strong expansion.

More precisely, one usually studies a family of graphs

where the number of vertices tends to infinity, the maximum degree remains bounded, and the expansion stays bounded away from zero.

A typical definition is this:

A family $(G_n)$ of $d$-regular graphs is an edge-expander family if there exists a constant

such that

for every graph in the family.

The constant $d$ controls sparsity. The constant $\varepsilon$ controls expansion.

This combination is important. Complete graphs have excellent expansion, but they are dense. A complete graph on $n$ vertices has

edges. Expanders aim for strong connectivity using only

edges.

52.5 Why Sparse Expansion Is Surprising

Sparse graphs normally seem fragile. A tree has only

edges, and every edge of a tree is a bridge. It has very poor edge expansion.

A cycle has

edges and no bridges, but its expansion is still small. If $S$ is a long consecutive segment of the cycle, then only two edges leave $S$. Therefore

can be very small.

An expander also has only linearly many edges, but no large set can be connected to the rest by only a few edges. It is sparse like a cycle, but globally connected like a random graph.

This is the distinctive feature of expanders.

52.6 Examples and Nonexamples

A path graph $P_n$ is not an expander family. If $S$ is the first $k$ vertices of the path, then only one edge leaves $S$. Hence

which tends to $0$ as $k$ grows.

A cycle graph $C_n$ is also not an expander family. A consecutive block of $k$ vertices has only two outgoing edges, so

This again tends to $0$.

A complete graph $K_n$ has very large expansion, but it is not sparse.

Random regular graphs are typical examples of expanders. For fixed degree $d$ large enough, a random $d$-regular graph usually has strong expansion. Explicit expander constructions are more difficult and form a major topic in combinatorics, number theory, and theoretical computer science.

52.7 Expansion and Cuts

Expansion can be viewed as a strengthened cut condition.

Edge connectivity only asks for the minimum number of edges in a cut:

Edge expansion asks for the ratio

This distinction matters.

A graph may have edge connectivity $3$, meaning that at least three edges must be removed to disconnect it. But it might have a set of one million vertices connected to the rest by only three edges. Such a graph has poor expansion.

Expansion rules out this kind of bottleneck. It requires the boundary to grow in proportion to the size of the set.

Expansion is therefore more global than ordinary connectivity.

52.8 Expansion and Random Walks

Expansion is closely related to random walks.

A random walk on a graph starts at a vertex and repeatedly moves to a random neighbor. On an expander, the walk spreads quickly through the graph.

Intuitively, this happens because every set has many edges leaving it. A walk trapped in a set has many opportunities to escape. Therefore it cannot remain confined for long unless the set is already large.

This property is often stated in terms of mixing. A random walk on a good expander approaches its stationary distribution rapidly.

For a regular graph, the stationary distribution is uniform. Thus a random walk on a regular expander quickly becomes close to uniformly distributed over the vertices.

This connection between expansion and rapid mixing is one reason expanders are important in algorithms and probability.

52.9 Spectral Expansion

Expansion can also be measured by eigenvalues.

Let $G$ be a $d$-regular graph with adjacency matrix $A$. Since $A$ is symmetric, its eigenvalues are real. They may be ordered as

The largest eigenvalue is

with the all-ones vector as an eigenvector.

The number

is called the spectral gap.

A large spectral gap indicates strong expansion. In a $d$-regular graph, expansion is quantitatively related to the gap between the largest eigenvalue and the next largest eigenvalue. These relationships are discrete analogues of Cheeger inequalities.

Spectral expansion is powerful because eigenvalues can often be estimated or computed using linear algebra.

52.10 The Normalized View

For a $d$-regular graph, it is often convenient to use the normalized adjacency matrix

This is also the transition matrix of the simple random walk.

Its eigenvalues are

where

The normalized spectral gap is

A larger gap means faster mixing and stronger expansion.

This normalized form is common in probability and algorithms because the matrix $P$ describes one step of the random walk.

52.11 Cheeger-Type Inequalities

For regular graphs, edge expansion and spectral expansion control each other.

A typical Cheeger-type inequality has the form

The exact constants vary with the chosen normalization and definition of expansion. The important point is structural: expansion is reflected in the spectrum, and the spectrum gives bounds on expansion.

This is one of the central bridges between graph theory and linear algebra.

Thus expanders can be studied either by counting edges across cuts or by analyzing eigenvalues.

52.12 Expander Mixing

A good expander behaves in some ways like a random graph.

One formal expression of this idea is the expander mixing principle. It says that in a good spectral expander, the number of edges between two vertex sets is close to what one would expect in a random-like regular graph.

If $G$ is $d$-regular on $n$ vertices, then the expected number of edges between sets $S$ and $T$ in a uniformly mixed model is approximately

A spectral expander has actual edge counts close to this value, with an error controlled by the nontrivial eigenvalues.

This is why expanders are often called pseudorandom graphs. They are deterministic sparse graphs that imitate certain random graph properties.

52.13 Construction of Expanders

Constructing expanders explicitly is difficult.

Random regular graphs are often expanders, but random existence does not automatically give a simple deterministic construction.

Several construction methods are known:

Ramanujan graphs are especially important spectral expanders. For a $d$-regular graph, the best possible asymptotic bound for nontrivial eigenvalues is tied to $2\sqrt{d-1}$, and Ramanujan graphs meet this bound.

52.14 Applications

Expanders appear throughout mathematics and computer science.

They are used in:

The original motivation includes economical robust networks, where bounded degree gives low cost and expansion gives fault tolerance. Expanders also have major applications in algorithms, coding theory, pseudorandomness, sorting networks, and computational complexity.

52.15 Common Mistakes

A common mistake is to think that high connectivity alone implies good expansion. It does not. Connectivity measures the smallest separating set. Expansion measures all cuts relative to the size of the smaller side.

Another mistake is to treat complete graphs as the main example. Complete graphs expand well, but they are dense. The point of expander theory is to obtain strong expansion with bounded degree.

A third mistake is to confuse edge expansion with vertex expansion. Edge expansion counts outgoing edges. Vertex expansion counts outside neighbors.

A fourth mistake is to assume that all sparse graphs are poor expanders. Paths and grids expand poorly, but carefully constructed sparse graphs may expand very well.

52.16 Summary

Expansion measures how strongly every small or medium-sized vertex set connects to the rest of the graph.

Expanders are sparse graphs with strong global connectivity. They refine the study of cuts by measuring not only whether a graph can be disconnected, but how every part of the graph is connected to its complement.