Expander Graphs, in depth: edge and spectral expansion, Cheeger and the mixing lemma checked in code, Ramanujan bounds, constructions and where expanders run

What expansion means

Take a graph G with n vertices, each of degree d. For a set S of vertices, the edge boundary is the set of edges with one end in S and one end outside. The edge expansion, also called the Cheeger constant, is the worst ratio over sets of at most half the graph: h(G) = min over |S| ≤ n/2 of |boundary(S)| / |S|. A family of d-regular graphs is an expander family if h stays above a fixed positive constant as n grows.

Compare a cycle, a grid and a random 3-regular graph. On a cycle of n vertices, let S be a contiguous arc of n/2 vertices: only 2 edges leave it, so h ≤ 4/n, which goes to zero. On a 32 by 32 grid, a half-grid has 32 boundary edges for 512 vertices, ratio 1/16. On a random 3-regular graph with 14 vertices, the brute-force minimum over all 9,907 sets with at most 7 vertices is 0.429: no such set has fewer than 3 boundary edges per 7 vertices. As n grows, random 3-regular graphs keep h above a fixed constant, which is what the definition asks for.

Vertex expansion counts boundary vertices instead of edges, and spectral expansion uses eigenvalues. For d-regular graphs with d fixed the three notions are equivalent up to constants, so algorithms use the one that is cheapest to compute, which is always the spectral one. Computing h exactly is NP-hard in general.

The spectral view

The adjacency matrix A of a d-regular graph is symmetric, so it has real eigenvalues d = λ1 ≥ λ2 ≥ ... ≥ λn. The top eigenvalue is d, with the all-ones eigenvector. The graph is connected exactly when λ2 is below d, and bipartite exactly when λn = -d. The spectral gap is d - λ2, and the two-sided quantity λ = max(|λ2|, |λn|) matters for random walks and edge counts.

• Cheeger inequality (d-regular form): (d - λ2)/2 ≤ h(G) ≤ sqrt(2d(d - λ2)). A gap bounded away from zero forces every cut to be large; a small gap means some cut is small. On the 14-vertex graph above, λ2 = 2.622, so the bounds are 0.189 ≤ h ≤ 1.506, and the brute-force h = 0.429 sits between them.
• Expander mixing lemma: for any sets S and T, counting ordered pairs (u in S, v in T) joined by an edge, |e(S, T) - d|S||T|/n| ≤ λ sqrt(|S||T|). The term d|S||T|/n is what a random graph of the same density would give, so a small λ means every pair of large sets has close to the expected number of edges. On the same graph, 20,000 random pairs used at most 40 percent of the allowed deviation.
• Alon-Boppana bound: for any infinite family of d-regular graphs, λ2 is at least 2 sqrt(d - 1) minus a term that goes to zero. No family beats that. Graphs with every nontrivial eigenvalue at most 2 sqrt(d - 1) in absolute value are called Ramanujan, the best possible expanders.
• Friedman's theorem: a random d-regular graph has λ at most 2 sqrt(d - 1) + ε with probability going to one. Random graphs are almost optimal, which the measurements below show.

Measuring a graph in code

The code below is the measurement kit. random_regular pairs half-edges at random and rejects loops and repeated edges; spectral_summary reads the gap; edge_expansion brute-forces h for small graphs, to check the theory; and lazy_mixing_time runs the walk that stays put with probability one half, which avoids the bipartite oscillation explained under failure modes.

import itertools, random
import numpy as np

def random_regular(n, d, rng=random):
    """Random simple d-regular graph by the pairing model; restarts if it gets stuck."""
    assert n * d % 2 == 0 and d < n
    while True:
        points = [v for v in range(n) for _ in range(d)]   # d half-edges per vertex
        edges, stuck = set(), False
        while points and not stuck:
            for _ in range(100):
                i, j = rng.randrange(len(points)), rng.randrange(len(points))
                a, b = points[i], points[j]
                e = (min(a, b), max(a, b))
                if i != j and a != b and e not in edges:     # no loops, no multi-edges
                    break
            else:
                stuck = True
                continue
            edges.add(e)
            for k in sorted((i, j), reverse=True):
                points.pop(k)
        if not stuck:
            return edges

def adjacency(n, edges):
    A = np.zeros((n, n))
    for a, b in edges:
        A[a, b] = A[b, a] = 1
    return A

def spectral_summary(A, d):
    ev = np.sort(np.linalg.eigvalsh(A))[::-1]               # d = ev[0] >= ev[1] >= ...
    lam = max(abs(ev[1]), abs(ev[-1]))
    return {"lambda2": ev[1], "lambda": lam, "gap": d - ev[1],
            "ramanujan_bound": 2 * np.sqrt(d - 1)}

def edge_expansion(A):
    """Exact h(G) = min over |S| <= n/2 of edges leaving S / |S|. Exponential: n <= 20."""
    n = len(A)
    best = float("inf")
    for k in range(1, n // 2 + 1):
        for S in itertools.combinations(range(n), k):
            out = np.ones(n, bool); out[list(S)] = False
            best = min(best, A[np.ix_(list(S), out)].sum() / k)
    return best

def lazy_mixing_time(A, eps=0.01, start=0):
    """Steps until the lazy walk from `start` is within eps of stationary (total variation)."""
    n = len(A)
    P = 0.5 * np.eye(n) + 0.5 * A / A.sum(1, keepdims=True)
    pi = A.sum(1) / A.sum()
    x = np.zeros(n); x[start] = 1
    t = 0
    while 0.5 * np.abs(x - pi).sum() >= eps:
        x = x @ P; t += 1
    return t

Results on 1,000-vertex random graphs, one draw each:

Every draw landed just under the Ramanujan bound, as Friedman's theorem predicts. Then the walk, on 1,024 vertices with ε = 0.01 from vertex 0: a random 4-regular graph mixed in 64 steps, a random 8-regular graph in 26, and the 32 by 32 grid, also 1,024 vertices with degree at most 4, took 3,472. In a separate draw, the grid's second-smallest Laplacian eigenvalue was about 0.0096 against 0.54 for a random 4-regular graph, and walk time scales with the inverse of that gap; breadth-first search from 16 sampled sources gave a largest distance of 8 for the 4-regular graph, 5 for an 8-regular one and 62 for the grid.

Why a gap gives fast mixing and short paths

For the lazy walk, P = (I + A/d)/2 has eigenvalues (1 + λi/d)/2. Every component of the starting distribution except the stationary one shrinks by a factor of at most 1 - (d - λ2)/(2d) per step, so after t steps the distance to uniform is at most sqrt(n) times that factor to the power t. Setting this below ε gives t = O(log(n/ε) · d / (d - λ2)). With the gap fixed, mixing takes logarithmically many steps. For a cycle the gap is about 4π²/n², which gives mixing time quadratic in n.

Diameter follows: once the walk from u reaches every vertex with positive probability, every vertex is within t hops, so expanders have diameter O(log n).

Constructions

There are three ways to get an expander, and they trade simplicity for guarantees.

In engineering the random construction usually wins because it is cheap to verify. The Margulis graph on Z_m × Z_m is the classic explicit example: in the Gabber-Galil form presented by Hoory, Linial and Wigderson, vertex (x, y) connects to (x ± 2y, y), (x ± (2y + 1), y), (x, y ± 2x) and (x, y ± (2x + 1)), all mod m. That is degree 8, with a few loops and repeated edges, and the survey proves λ2 ≤ 5 sqrt(2), about 7.07, for every m; computed directly, λ2 is 6.30 at m = 32. Use it when the graph is too large to store.

Where expanders are used

Four uses show how widely the property travels.

• Data-centre networks. Jellyfish (Singla and colleagues, NSDI 2012) wires top-of-rack switches as a random regular graph instead of a fat tree, getting more throughput from the same equipment because paths are short and no cut is a bottleneck. Xpander (CoNEXT 2016) uses lifts of a complete graph to get comparable expansion with simpler cabling. The price is routing: shortest paths are not enough, and these designs rely on k-shortest-path or multipath routing.
• Error-correcting codes. Sipser and Spielman's expander codes put bits on the edges or left vertices of an expander and parity checks on the other side. Expansion guarantees that a small error pattern violates many checks, so a simple flip-the-worst-bit decoder runs in linear time.
• Saving random bits. Sampling t independent points from a space of size N costs t log N random bits. Taking t steps of a walk on a d-regular expander over the same space costs log N + t log d bits, and by Chernoff bounds for expander walks the sample mean is almost as concentrated. This is the same idea as pairwise independence, buying near-independence with fewer random bits.
• Sparse attention on graphs. Exphormer (Shirzad and colleagues, ICML 2023) adds the edges of a random regular expander to a graph transformer's attention pattern, so information can cross the graph in a few layers while attention stays linear in the number of nodes. The same reasoning explains why HNSW and other navigable graphs add long-range links: they cut the hop count to logarithmic.

Operating an expander topology

If you are building an overlay, a peer-to-peer mesh or a switch fabric as an expander, treat the gap as a service-level indicator.

1. Generate, then verify. Build the graph with the pairing model and reject it if λ is more than a few percent above 2 sqrt(d - 1). Store the edge list and the measured λ with the build.
2. Grow by edge splitting. To add a vertex to a d-regular graph with d even, pick d/2 random existing edges (a, b), delete each one, and add (a, new) and (new, b). Every degree stays d, and in practice the gap stays close to a fresh draw; re-measure λ after each batch of additions.
3. Measure at scale with a sparse solver. Dense eigvalsh costs O(n³) time and n² memory, which is fine at a few thousand vertices. Beyond that use Lanczos iteration on the sparse matrix, for example scipy.sparse.linalg.eigsh(A, k=3, which='LA') for the top eigenvalues and which='SA' for the bottom one.
4. Re-measure after failures. Each lost link removes one unit of degree from two vertices. Clustered failures can open a small cut, which a BFS from each region will not reveal but the gap will.

Failure modes

• Multi-edges and loops. The naive configuration model pairs half-edges freely, and for d = 8 almost every draw contains a loop or repeated edge, so retrying the whole draw until it is simple can loop for a very long time. The code above rejects bad pairs locally instead.
• Reading only λ2. A bipartite graph has λn = -d, so a plain walk oscillates between the two sides and never converges, even with a large gap. Use λ = max(|λ2|, |λn|) for mixing claims, or make the walk lazy.
• Disconnected graphs. λ2 = d exactly. A random draw is connected with high probability for d at least 3, but a graph assembled by hand or damaged by failures may not be. Check connectivity first.
• Averages hide small cuts. A good mean distance or a fast average mixing time does not rule out a small set with few exits. Only the gap, or an explicit cut search, bounds the worst set.
• Physical cost ignored. Random wiring has no locality. In a data centre that means long cables and hard maintenance; in a distributed system it means cross-region links.

What to do next

1. Run the measurement kit for d = 3, 4 and 8 and confirm that λ lands just under 2 sqrt(d - 1).
2. Brute-force h on a 14-vertex graph and check both sides of the Cheeger inequality.
3. Build the Margulis graph for m = 32 and compare its gap with a random 8-regular graph on 1,024 vertices.
4. Delete 10 percent of edges at random, then 10 percent from one region, and compare λ2 after each.
5. Read random walks for hitting and cover times, then try the expander-walk sampler on a Monte Carlo estimate.