Expander graph

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

Definitions

Intuitively, an expander graph is a finite, undirected multigraph in which every subset of the vertices that is not "too large" has a "large" boundary. Different formalisations of these notions give rise to different notions of expanders: edge expanders, vertex expanders, and spectral expanders, as defined below.
A disconnected graph is not an expander, since the boundary of a connected component is empty. Every connected finite graph is an expander; however, different connected graphs have different expansion parameters. The complete graph has the best expansion property, but it has largest possible degree. Informally, a graph is a good expander if it has low degree and high expansion parameters.

Edge expansion

The edge expansion of a graph on vertices is defined as
which can also be written as with the complement of and
the edges between the subsets of vertices.
In the equation, the minimum is over all nonempty sets of at most vertices and is the edge boundary of, i.e., the set of edges with exactly one endpoint in.
Intuitively,
is the minimum number of edges that need to be cut in order to split the graph in two.
The edge expansion normalizes this concept by dividing with smallest number of vertices among the two parts.
To see how the normalization can drastically change the value, consider the following example.
Take two complete graphs with the same number of vertices and add edges between the two graphs by connecting their vertices one-to-one.
The minimum cut will be but the edge expansion will be 1.
Notice that in, the optimization can be equivalently done either over or over any non-empty subset, since . The same is not true for because of the normalization by.
If we want to write with an optimization over all non-empty subsets, we can rewrite it as

Vertex expansion

The vertex isoperimetric number of a graph is defined as
where is the outer boundary of, i.e., the set of vertices in with at least one neighbor in. In a variant of this definition is replaced by the set of vertices in with exactly one neighbor in.
The vertex isoperimetric number of a graph is defined as
where is the inner boundary of, i.e., the set of vertices in with at least one neighbor in.

Spectral expansion

When is -regular, a linear algebraic definition of expansion is possible based on the eigenvalues of the adjacency matrix of, where is the number of edges between vertices and. Because is symmetric, the spectral theorem implies that has real-valued eigenvalues. It is known that all these eigenvalues are in and more specifically, it is known that if and only if is bipartite.
More formally, we refer to an -vertex, -regular graph with
as an -graph. The bound given by an -graph on for is useful in many contexts, including the expander mixing lemma.
Spectral expansion can be two-sided, as above, with, or it can be one-sided, with. The latter is a weaker notion that holds also for bipartite graphs and is still useful for many applications, such as the Alon–Chung lemma.
Because is regular, the uniform distribution with for all is the stationary distribution of. That is, we have, and is an eigenvector of with eigenvalue, where is the degree of the vertices of. The spectral gap of is defined to be, and it measures the spectral expansion of the graph.
If we set
as this is the largest eigenvalue corresponding to an eigenvector orthogonal to, it can be equivalently defined using the Rayleigh quotient:
where
is the 2-norm of the vector.
The normalized versions of these definitions are also widely used and more convenient in stating some results. Here one considers the matrix, which is the Markov transition matrix of the graph. Its eigenvalues are between −1 and 1. For not necessarily regular graphs, the spectrum of a graph can be defined similarly using the eigenvalues of the Laplacian matrix. For directed graphs, one considers the singular values of the adjacency matrix, which are equal to the roots of the eigenvalues of the symmetric matrix.

Expander families

A family of -regular graphs of increasing size is an expander family if is bounded away from zero.

Relationships between different expansion properties

The expansion parameters defined above are related to each other. In particular, for any -regular graph,
Consequently, for constant degree graphs, vertex and edge expansion are qualitatively the same.

Cheeger inequalities

When is -regular, meaning each vertex is of degree, there is a relationship between the isoperimetric constant and the gap in the spectrum of the adjacency operator of. By standard spectral graph theory, the trivial eigenvalue of the adjacency operator of a -regular graph is and the first non-trivial eigenvalue is. If is connected, then. An inequality due to Dodziuk and independently Alon and Milman states that
In fact, the lower bound is tight. The lower bound is achieved in limit for the hypercube, where and. The upper bound is achieved for a cycle, where and. A better bound is given in as
These inequalities are closely related to the Cheeger bound for Markov chains and can be seen as a discrete version of Cheeger's inequality in Riemannian geometry.
Similar connections between vertex isoperimetric numbers and the spectral gap have also been studied:
Asymptotically speaking, the quantities,, and are all bounded above by the spectral gap.

Constructions

There are four general strategies for explicitly constructing families of expander graphs. The first strategy is algebraic and group-theoretic, the second strategy is analytic and uses additive combinatorics, the third strategy is combinatorial and uses the zig-zag and related graph products, and the fourth strategy is based on [|lifts]. Noga Alon showed that certain graphs constructed from finite geometries are the sparsest examples of highly expanding graphs.

Margulis–Gabber–Galil

constructions based on Cayley graphs are known for various variants of expander graphs. The following construction is due to Margulis and has been analysed by Gabber and Galil. For every natural number, one considers the graph with the vertex set, where : For every vertex, its eight adjacent vertices are
Then the following holds:

Theorem. For all, the graph has second-largest eigenvalue.

Ramanujan graphs

By a theorem of Alon and Boppana, all sufficiently large -regular graphs satisfy, where is the second largest eigenvalue in absolute value. As a direct consequence, we know that for every fixed and , there are only finitely many -graphs. Ramanujan graphs are -regular graphs for which this bound is tight, satisfying
Hence Ramanujan graphs have an asymptotically smallest possible value of. This makes them excellent spectral expanders.
Lubotzky, Phillips, and Sarnak, Margulis, and Morgenstern show how Ramanujan graphs can be constructed explicitly.
In 1985, Alon, conjectured that most -regular graphs on vertices, for sufficiently large, are almost Ramanujan. That is, for, they satisfy
In 2003, Joel Friedman both proved the conjecture and specified what is meant by "most -regular graphs" by showing that random -regular graphs have for every with probability, where
A simpler proof of a slightly weaker result was given by Puder.
Marcus, Spielman and Srivastava, gave a construction of bipartite Ramanujan graphs based on lifts.
In 2024 a preprint by Jiaoyang Huang, Theo McKenzieand and Horng-Tzer Yau proved that
with the fraction of eigenvalues that hit the Alon-Boppana bound approximately 69% from proving that edge universality holds, that is they follow a Tracy-Widom distribution associated with the Gaussian Orthogonal Ensemble

Zig-zag product

, Vadhan, and Wigderson introduced the zig-zag product in 2003. Roughly speaking, the zig-zag product of two expander graphs produces a graph with only slightly worse expansion. Therefore, a zig-zag product can also be used to construct families of expander graphs. If is a -graph and is an -graph, then the zig-zag product is a -graph where has the following properties.

If and, then ;
.

Specifically,
Note that property implies that the zig-zag product of two expander graphs is also an expander graph, thus zig-zag products can be used inductively to create a family of expander graphs.
Intuitively, the construction of the zig-zag product can be thought of in the following way. Each vertex of is blown up to a "cloud" of vertices, each associated to a different edge connected to the vertex. Each vertex is now labeled as where refers to an original vertex of and refers to the th edge of. Two vertices, and are connected if it is possible to get from to through the following sequence of moves.

Zig – Move from to, using an edge of.
Jump across clouds using edge in to get to.
Zag – Move from to using an edge of.
Lifts

An -lift of a graph is formed by replacing each vertex by vertices, and each edge by a matching between the corresponding sets of vertices. The lifted graph inherits the eigenvalues of the original graph, and has some additional eigenvalues. Bilu and Linial showed that every -regular graph has a 2-lift in which the additional eigenvalues are at most in magnitude. They also showed that if the starting graph is a good enough expander, then a good 2-lift can be found in polynomial time, thus giving an efficient construction of -regular expanders for every.
Bilu and Linial conjectured that the bound can be improved to, which would be optimal due to the Alon–Boppana bound. This conjecture was proved in the bipartite setting by Marcus, Spielman and Srivastava, who used the method of interlacing polynomials. As a result, they obtained an alternative construction of bipartite Ramanujan graphs. The original non-constructive proof was turned into an algorithm by Michael B. Cohen. Later the method was generalized to -lifts by Hall, Puder and Sawin.