Fact-checked by Grok 2 weeks ago

Expander graph

An expander graph is a sparse, regular graph with strong expansion properties, ensuring that every small subset of vertices has a disproportionately large number of neighbors outside that subset, which can be quantified through combinatorial, geometric, probabilistic, or algebraic measures.^[1] These graphs, often denoted as (n, d, α)-expanders where n is the number of vertices, d is the fixed degree, and α < 1 measures the expansion quality, were first conceptualized in the context of error-correcting codes and have since become fundamental structures in theoretical computer science and combinatorics.^[1] The key properties of expander graphs include high connectivity in the combinatorial sense, where the edge expansion ratio h(G) = min_{|S| ≤ n/2} |E(S, \bar{S})| / |S| is bounded below by a positive constant; geometrically, small vertex sets have large boundaries; probabilistically, random walks on the graph mix rapidly to a uniform distribution; and algebraically, the spectral gap of the adjacency matrix—the difference between the largest eigenvalue d and the second-largest |λ|—is at least a fixed positive value, often with |λ| ≤ d(1 - α).^[1] These equivalent characterizations enable expander graphs to exhibit small diameter, vertex-transitivity in explicit constructions like Cayley graphs, and resilience to vertex or edge failures.^[1] Historically, the idea emerged in Robert Gallager's 1963 work on low-density parity-check (LDPC) codes using random graphs with good expansion.^[2] The formal definition appeared in the early 1970s through probabilistic existence proofs by A. G. Pinsker and L. A. Bassalygo, followed by G. A. Margulis's 1973 explicit construction via Cayley graphs on SL_3(p) groups, leveraging Kazhdan's property (T).^[1] Subsequent advances in the 1980s and 1990s, including bounds by Gabber and Galil and spectral methods by Lubotzky, Phillips, and Sarnak, solidified their theoretical foundations and explicit constructions.^[1] Expander graphs find broad applications in error-correcting codes, such as asymptotically good LDPC codes for reliable data transmission; pseudorandomness and derandomization in algorithms; complexity theory, including proofs like SL = L; network design for efficient routing and fault tolerance; metric embeddings into Euclidean spaces; and Monte Carlo methods in statistical physics for sampling. Recent developments, such as high-dimensional expander graphs and explicit lossless constructions (as of 2025), continue to expand their applications in quantum error correction and advanced sampling techniques.^[3] Their versatility stems from the ability to simulate random-like behavior with deterministic structures, impacting fields from cryptography to parallel computing over the past five decades.^[1]

Introduction

Overview

Expander graphs are sparse graphs that exhibit remarkably strong connectivity properties despite having a limited number of edges per vertex, allowing small sets of vertices to rapidly "expand" into much larger neighborhoods and enabling efficient mixing of information across the graph.^[1] Intuitively, they mimic the robust connectivity of dense complete graphs but with far fewer edges, making them valuable for modeling systems where resources like bandwidth or computation must be minimized while preserving high performance in spreading signals or random walks.^[4] The concept originated in the early 1970s, with Mark Pinsker demonstrating in 1973 that random regular graphs are expanders with high probability, providing the first existence proof for such structures in the context of concentrator networks.^[1]^[4] This probabilistic approach highlighted that most sparse graphs behave as expanders, laying the groundwork for explicit constructions that followed.^[1] In theoretical computer science, expander graphs have profound impacts, serving as building blocks for derandomization techniques that convert probabilistic algorithms into deterministic ones with minimal overhead, such as in Reingold's proof that symmetric log-space equals nondeterministic log-space.^[1] They also underpin efficient error-correcting codes, like low-density parity-check codes, which achieve near-optimal rates and enable reliable data transmission over noisy channels with linear-time decoding.^[1]

Historical Development

The concept of expander graphs emerged in the early 1970s through probabilistic arguments demonstrating their existence. In 1973, Mark S. Pinsker and independently L. A. Bassalygo proved, using the probabilistic method, that random regular graphs exhibit strong expansion properties, providing the first non-constructive evidence for the existence of families of expander graphs with positive expansion constants.^[5] This work laid the foundational insight that sparse graphs could achieve near-optimal connectivity akin to random graphs, though explicit constructions remained elusive.^[1] The first explicit construction appeared shortly thereafter in 1973, when Gregory Margulis introduced a family of Cayley graphs based on the special linear group \mathrm{SL}_3(\mathbb{F}_p) over finite fields \mathbb{F}_p that serve as expanders.^[6] Margulis's approach leveraged group-theoretic properties to generate infinite families of constant-degree expanders, marking a pivotal shift from probabilistic existence to deterministic designs suitable for applications in network theory.^[1] During the 1980s, refinements focused on improving expansion guarantees and efficiency. Ofer Gabber and Zvi Galil provided an elementary analysis and construction of linear-sized superconcentrators based on Margulis's graphs, establishing explicit bounds on the second-largest eigenvalue to confirm their expander quality.^[1] This was followed in 1988 by Alexander Lubotzky, Ralph Phillips, and Peter Sarnak, who constructed Ramanujan graphs—optimal expanders achieving the Alon-Boppana bound on spectral expansion—using Cayley graphs of PGL(2, q) for prime powers q, resolving a major conjecture in spectral graph theory.^[7] The 1990s and 2000s saw expander graphs integrated into complexity theory, particularly for derandomization. A landmark contribution came in 2002 from Omer Reingold, Salil Vadhan, and Avi Wigderson, who introduced the zig-zag graph product, enabling the recursive construction of constant-degree expanders from smaller ones and facilitating explicit families with near-optimal spectral gaps.^[8] This tool proved instrumental in derandomizing algorithms, including Reingold's 2005 proof that undirected connectivity is in logarithmic space (SL = L). A key early application was the 1983 Ajtai-Komlós-Szemerédi (AKS) sorting network, which employed expander graphs to achieve O(n log n) size and logarithmic depth, demonstrating parallel sorting in NC and influencing subsequent complexity separations like NC¹ ⊆ SL. In the 2020s, advances have targeted specialized expansion notions. In 2025, Rachel Zhang and collaborators constructed the first explicit constant-degree lossless vertex expanders, where small vertex sets expand to nearly their full possible neighborhood size, surpassing spectral limitations for vertex expansion.^[3] Concurrently, Alan Lew, Eran Nevo, Yuval Peled, and others introduced rigidity expander graphs, generalizing spectral expansion to quantify d-dimensional rigidity via algebraic connectivity of stiffness matrices, with explicit constructions achieving strong rigidity bounds.^[9] These developments highlight the ongoing evolution of expander graphs toward broader geometric and structural applications.

Definitions

Edge Expansion

In a d-regular graph G = (V, E) with n = |V| vertices, the edge expansion h(G), also known as the Cheeger constant, is defined as

h(G) = \min_{\substack{S \subseteq V \\ |S| \leq n/2}} \frac{|E(S, V \setminus S)|}{|S|},

where E(S, V \setminus S) denotes the number of edges with one endpoint in S and the other in V \setminus S.^[1] This measure is bounded above by d, as the maximum possible crossing edges is d |S|.^[1] Combinatorially, edge expansion quantifies the graph's resistance to bottlenecks by measuring the minimum number of edges that must be cut to isolate a small subset S from the rest of the graph, normalized by the size of S. A large h(G) ensures that every reasonably sized set S has many outgoing edges, promoting uniform mixing and robust connectivity, which is essential for applications like error-correcting codes and network design.^[1] For the complete graph K_n, which is (n-1)-regular, h(K_n) = n/2, achieved at |S| = n/2 where all possible cross-edges exist. In contrast, the n-vertex cycle graph C_n, which is $2-regular, has h(C_n) = 4/n, as a contiguous half-cycle Swith|S| = n/2$ has only two outgoing edges.^[1] Edge expansion connects to the vertex-isoperimetric problem, which seeks to minimize the vertex boundary |\Gamma(S) \setminus S| for sets of fixed size k \leq n/2, providing a vertex-based analogue to the edge boundary measure.^[1]

Vertex Expansion

Vertex expansion is a combinatorial measure of a graph's connectivity that quantifies how rapidly the neighborhoods of small vertex sets grow. Formally, for a graph G = (V, E) with n = |V|, the vertex expansion h_v(G) is defined as

h_v(G) = \min_{\substack{S \subseteq V \\ |S| \leq n/2}} \frac{|N(S)|}{|S|},

where N(S) denotes the external neighborhood of S, consisting of all vertices adjacent to at least one vertex in S but excluding those in S itself.^[1] This metric captures the minimum expansion factor achieved by any sufficiently small subset of vertices, ensuring that no "bottleneck" set isolates a portion of the graph from the rest. In contrast to edge expansion, which counts the number of edges crossing from a set to its complement, vertex expansion emphasizes the diversity of reachable vertices rather than the volume of connections. This distinction is crucial because vertex expansion directly relates to the graph's ability to connect sets via distinct paths, independent of edge multiplicity. For instance, in a d-regular graph, strong vertex expansion implies that small sets can access a large fraction of the vertex set quickly, facilitating applications like efficient routing.^[1] A canonical example of a graph with strong vertex expansion for small sets is the d-dimensional hypercube Q_d, where the neighborhood of a small set S can grow to nearly d |S| distinct external vertices. However, the overall h_v(Q_d) = 1, as for the balanced bipartition |S| = n/2, |N(S)| = n/2. Conversely, trees, such as finite d-regular trees, exhibit poor vertex expansion globally; while small sets near the root may expand well, sets deeper in the structure often have |N(S)| \approx |S|, leading to bottlenecks that prevent uniform connectivity across the graph.^[1] Graphs are often classified using the parameterized notion of (K, A)-vertex expanders, where A > 1 is the expansion factor and K \leq n/2 bounds the set size: every S \subseteq V with |S| \leq K satisfies |N(S)| \geq A |S|. This framework allows for tailored constructions in expander families, ensuring controlled growth for subsets up to a specified scale, as seen in lossless expanders where A approaches the degree d for K = \Theta(n).^[1]

Spectral Expansion

Spectral expansion provides an algebraic measure of a graph's connectivity by examining the eigenvalues of its adjacency matrix. For an undirected d-regular graph G with n vertices, the adjacency matrix A is a symmetric n \times n matrix where A_{ij} = 1 if vertices i and j are adjacent, and $0otherwise. The eigenvalues ofAare real numbers\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n, satisfying -d \leq \lambda_i \leq dfor alli. The largest eigenvalue \lambda_1 = d$ is trivial, corresponding to the all-ones eigenvector, which reflects the graph's regularity.^[1] The spectral gap of G is defined as d - \lambda_2, where \lambda_2 is the second-largest eigenvalue. This gap quantifies how much the graph deviates from being disconnected or poorly connected; a larger gap indicates stronger global mixing properties. A d-regular graph G is considered a spectral expander if \lambda_2 \leq d(1 - \varepsilon) for some fixed \varepsilon > 0 independent of n. More generally, the expansion parameter is \lambda = \max(|\lambda_2|, |\lambda_n|), and G exhibits spectral expansion if \lambda < d, meaning the nontrivial eigenvalues are bounded away from the trivial one in absolute value.^[1] Spectral expansion is closely tied to the behavior of random walks on the graph. The transition matrix for a simple random walk is P = A/d, with eigenvalues \mu_i = \lambda_i / d, so the second-largest eigenvalue in absolute value is \mu = \lambda / d < 1. The mixing time, or the number of steps required for the walk to approach the stationary uniform distribution within total variation distance \varepsilon, is bounded by O\left( \frac{\log(n/\varepsilon)}{1 - \mu} \right) = O\left( \frac{d \log(n/\varepsilon)}{d - \lambda} \right). Thus, a constant spectral gap ensures polylogarithmic mixing time, enabling efficient sampling and derandomization applications.^[1]

Expander Families

An expander family is an infinite collection of finite graphs \{G_N\}_{N \in S}, where S \subseteq \mathbb{N} is an infinite set, each G_N has N vertices and is d-regular for some fixed degree d \geq 3, and the number of vertices tends to infinity as N increases.^[10] Such families exhibit uniform expansion properties across all members, meaning that for every G_N in the family, the edge expansion h(G_N) satisfies h(G_N) \geq h > 0 for some fixed h, or equivalently in the spectral sense, the second-largest eigenvalue magnitude \lambda(G_N) \leq \lambda < d.^[10] This uniformity ensures that the graphs remain well-connected despite growing in size, with the expansion parameter bounded away from zero independently of N.^[11] Constructions of expander families are classified as explicit or non-explicit based on computability. An explicit expander family admits a polynomial-time algorithm that, given N \in S in binary, outputs either the full adjacency list of G_N (mildly explicit) or allows efficient neighbor queries for any vertex (strongly explicit).^[10] In contrast, non-explicit families rely on probabilistic existence proofs, such as those showing that random d-regular graphs on N vertices are expanders with high probability for sufficiently large N.^[10] Lossless expanders form a subclass of expander families optimized for near-ideal expansion on small vertex sets. Specifically, a d-regular bipartite graph G = (L \cup R, E) in such a family is a (\mu, \epsilon)-lossless expander if, for every subset S \subseteq L with |S| \leq \mu |L|, the neighborhood satisfies |N_G(S)| \geq (1 - \epsilon) d |S|.^[12] This property ensures that outgoing edges from small sets reach nearly the maximum possible distinct neighbors, minimizing collisions and preserving entropy in applications like coding theory and pseudorandomness.^[11] Explicit constructions of constant-degree lossless expander families have been developed, achieving expansion close to the random graph optimum for sets up to a constant fraction of the vertex set.^[12]

Relationships Between Expansion Measures

Cheeger Inequalities

The Cheeger inequalities provide a fundamental connection between the combinatorial edge expansion h(G) of a d-regular graph G and its spectral gap d - \lambda_2, where \lambda_2 is the second-largest eigenvalue of the adjacency matrix of G.^[13] These inequalities, discrete analogs of results in Riemannian geometry, establish that strong spectral expansion implies strong combinatorial expansion, and conversely, up to constant factors.^[13] The discrete Cheeger inequality states that for any connected d-regular graph G,

\frac{h(G)^2}{2d} \leq d - \lambda_2 \leq 2 h(G),

where h(G) is the edge expansion of G.^[13] The left inequality (lower bound on the spectral gap) is the harder direction and was independently established by Dodziuk and by Alon and Milman; it shows that graphs with large edge expansion must have a spectral gap bounded below by a quadratic function of the expansion.^[13] The right inequality (upper bound on the spectral gap) is a discrete adaptation of Buser's converse to Cheeger's inequality in manifolds and follows more directly. A sketch of the proof for the upper bound uses the Rayleigh quotient characterization of \lambda_2: for the eigenvector f corresponding to \lambda_2, normalized so that \sum_v f(v)^2 = 1, the quadratic form \sum_{uv \in E} (f(u) - f(v))^2 = d - \lambda_2 can be bounded above using the expander mixing lemma or by partitioning vertices based on level sets of f, yielding d - \lambda_2 \leq 2 h(G).^[13] For the lower bound, one applies a co-area formula-like argument to the level sets of the eigenvector f, integrating over thresholds to relate the Dirichlet energy to the minimum cut, resulting in the quadratic dependence \frac{h(G)^2}{2d} \leq d - \lambda_2.^[13] These inequalities imply that a family of d-regular graphs is a spectral expander (with d - \lambda_2 \geq \Omega(d)) if and only if it is a combinatorial expander (with h(G) \geq \Omega(1)), up to constant factors in the expansion parameters.^[13] This equivalence facilitates the use of spectral methods to certify and construct expander graphs, as computing eigenvalues is often more tractable than directly verifying edge expansion.

Comparisons and Equivalences

The edge expansion h and vertex expansion h_v of a d-regular graph are related by the bound h_v \geq h / d, where h = \min_{|S| \leq n/2} |E(S, \overline{S})| / |S| and h_v = \min_{|S| \leq n/2} |N(S)| / |S|. This follows because the edges leaving S can connect to each neighbor in \overline{S} by at most d edges, so |N(S)| \geq |E(S, \overline{S})| / d.^[14] The converse bound is weaker in general, as |E(S, \overline{S})| \geq |N(S) \cap \overline{S}| in simple graphs, yielding h \geq h_v - 1 for expansions exceeding 1, but without a tight linear relation.^[15] Spectral expansion, defined via the second-largest eigenvalue \lambda_2 of the adjacency matrix (with gap \gamma = 1 - \lambda_2 / d), implies both edge and vertex expansion, but with quadratic losses in the constants for vertex. Specifically, a d-regular graph with spectral expansion \gamma is an edge expander with h \geq d \gamma / 2 and a vertex expander with h_v \geq 1 + \Omega(\gamma).^[15]^[16] Conversely, edge expansion h implies spectral expansion \gamma \geq \Omega(h^2 / d^2), and vertex expansion h_v implies \gamma \geq \Omega((h_v / d)^2). These quadratic factors highlight that the measures are equivalent up to constants for constant-degree graphs but diverge when optimizing expansion parameters.^[15] Note that some sources define relative edge expansion h' = h / d \leq 1, in which case the bounds are stated directly in terms of h' and \gamma (e.g., h' \geq \gamma / 2).^[16] In bipartite graphs, edge and vertex expansions are particularly closely related, often differing by at most a factor of 1 in left-regular settings. For a d-left-regular bipartite graph with parts L and R (|L| = |R|), the vertex expansion for subsets S \subseteq L satisfies |N(S)| / |S| \geq 1 + \epsilon if and only if the normalized edge expansion |E(S, R \setminus N(S))| / (d |S|) \geq \epsilon, since all edges from S target distinct neighbors in R. This equivalence makes bipartite expanders interchangeable for applications like coding theory, where either measure ensures efficient neighbor growth.^[15] The Alon–Schwartz–Shapira theorem demonstrates that constructions achieving optimal vertex expansion also yield near-optimal spectral expansion via the replacement product, preserving expansion properties without algebraic machinery. Their approach shows that a vertex expander with parameters [n, D, \delta_1] combined with a small expander yields a constant-degree graph with spectral gap bounded by \Omega(\delta_1^2 / \poly(d)).^[17] While the measures align asymptotically for many families, they can differ significantly in constants. Random d-regular graphs expand well under all measures with high probability: they achieve vertex expansion nearly d - 1, edge expansion \Omega(d), and spectral gap \Omega(1) approaching the Ramanujan bound of d - 2\sqrt{d-1}.^[15] In contrast, Ramanujan graphs attain the optimal bound on the second-largest eigenvalue O(\sqrt{d}), yielding a spectral gap of d - O(\sqrt{d}) and vertex expansion \Theta(d), close to that of random graphs.^[15]^[16]

Constructions

Margulis–Gabber–Galil Construction

The Margulis–Gabber–Galil construction yields an explicit infinite family of constant-degree expander graphs using algebraic methods based on the special linear group \mathrm{SL}(2, \mathbb{Z}). The vertices of the graph G_m are elements of \mathbb{Z}_m \times \mathbb{Z}_m, where m is a positive integer, giving m^2 vertices in total. Each vertex (x, y) connects to eight neighbors defined by right multiplication (modulo m) by specific generators of \mathrm{SL}(2, \mathbb{Z}) and translations: specifically, the matrices T_1 = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix} and T_2 = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix}, their inverses, and shifts by the standard basis vectors e_1 = (1, 0) and e_2 = (0, 1).^[1] This setup corresponds to the Cayley graph of the finite quotient of the semidirect product \mathbb{Z}^2 \rtimes \mathrm{SL}(2, \mathbb{Z}), where the group operation combines vector addition with matrix action, resulting in an 8-regular graph.^[1] Vertices and edges can be labeled and computed in polynomial time relative to \log m, ensuring the family is explicitly constructible for arbitrarily large m.^[1] The construction was introduced by Margulis in 1973 as the first explicit family of expander graphs.^[1] Gabber and Galil provided an improved elementary analysis in 1981, proving strong spectral expansion using Fourier analysis.^[1] For the normalized adjacency matrix, the second-largest eigenvalue in absolute value satisfies \lambda(G_m) \leq 5\sqrt{2} \approx 7.07 < 8, yielding a constant spectral gap independent of m.^[1] This bound implies vertex and edge expansion parameters bounded away from zero, confirming the family consists of expanders.^[1] The proof of expansion leverages the non-commutative structure of \mathrm{SL}(2, \mathbb{Z}) within the semidirect product to bound eigenvalues using Fourier analysis on the abelian quotient \mathbb{Z}_m^2.^[1] Specifically, the adjacency operator is decomposed into translation and multiplication components; the Rayleigh quotient for non-constant eigenfunctions is analyzed via Parseval's identity and a partial order on frequencies, showing that the mixing induced by the non-commuting generators prevents concentration on low-frequency modes.^[1] This approach exploits the group's structure to ensure that irreducible representations beyond the trivial one have bounded norms under the generators, leading to the uniform spectral bound.^[1]

Ramanujan Graphs

Ramanujan graphs are d-regular graphs whose absolute values of the nontrivial eigenvalues of the adjacency matrix are at most $2\sqrt{d-1}.^[7] This definition achieves the optimal spectral expansion possible for d-regular graphs, as established by the Alon–Boppana bound, which proves that in any infinite family of d-regular graphs on n vertices, the largest nontrivial eigenvalue \lambda satisfies \lambda \geq 2\sqrt{d-1} - O(\sqrt{d}/\log d) as n \to \infty.^[13] Such graphs provide the strongest known explicit constructions for spectral expanders, maximizing the spectral gap relative to the degree.^[7] The foundational explicit construction of Ramanujan graphs was introduced by Lubotzky, Phillips, and Sarnak in 1988.^[7] They built infinite families of (p+1)-regular Ramanujan graphs, where p is a prime congruent to 1 modulo 4, as Cayley graphs \mathrm{Cay}(\mathrm{PGL}(2,q),\mathcal{S}) with q = p.^[7] Here, \mathrm{PGL}(2,q) is the projective general linear group over the finite field \mathbb{F}_q, and the generating set \mathcal{S} consists of (p-1)/2 elements each corresponding to matrices of the form \begin{pmatrix} a & b \\ c & d \end{pmatrix} where ad - bc = 1, b \neq 0, and a, b, c, d \in \mathbb{F}_q^* are quadratic residues or non-residues in a specific balanced way to ensure symmetry and connectivity.^[7] The vertex set has size q(q^2-1), yielding graphs of order growing with q.^[7] The proof that these Cayley graphs are Ramanujan relies on deep number-theoretic tools, specifically the eigenvalues of the adjacency operator, which are expressed in terms of Hecke operators acting on cusp forms of weight 2 for the full modular group \mathrm{SL}(2,\mathbb{Z}).^[7] By Deligne's proof of the Ramanujan–Petersson conjecture, the Fourier coefficients (Ramanujan tau function) of the associated modular form satisfy |\tau(p)| \leq 2p^{1/2}, which directly bounds the nontrivial eigenvalues of the graphs by $2\sqrt{p}.^[7] This connection between modular forms and graph spectra ensures the construction meets the Alon–Boppana bound exactly.^[7] Morgenstern extended this construction in 1994 to produce infinite families of (q+1)-regular Ramanujan graphs for every prime power q \equiv 1 \pmod{4}. His method generalizes the generating sets in Cayley graphs of \mathrm{PGL}(2,q') for suitable extensions q' of q, preserving the eigenvalue bounds via analogous properties of Hecke operators over function fields or finite fields. These extensions cover all degrees d \geq 3 where d-1 is a prime power congruent to 1 modulo 4, providing explicit Ramanujan graphs for a broad range of parameters.

Zig-Zag Product

The zig-zag product is a graph composition operation introduced to construct large expander graphs from smaller ones while preserving expansion properties. Given a d-regular graph G on n vertices and an e-regular graph H on d vertices, the zig-zag product G \times_z H has vertex set V(G) \times V(H), yielding n \cdot d vertices in total.^[18] The product graph is e^2-regular, as each vertex in the product connects through two steps in H.^[18] The edges in G \times_z H are defined via a three-step process that alternates between the two graphs, simulating a "zig-zag" walk. Label the neighbors of each vertex v \in V(G) as $1, 2, \dots, d, so V(H) = indexes these directions. From a vertex (v, i) \in V(G \times_z H), select a neighbor j of i in H (the "zig" step), move to the intermediate (v, j), then traverse the j-th outgoing edge from v in G to a neighbor v' (the "jump" step), and finally select a neighbor k of j in H (the "zag" step), arriving at (v', k). This construction ensures the product remains undirected if both input graphs are.^[18] The zig-zag product preserves spectral expansion: if G is an (n, d, \lambda_G)-expander and H is a (d, e, \lambda_H)-expander with \lambda_G, \lambda_H < 1, then G \times_z H is an (n d, e^2, \lambda)-expander where \lambda \leq \lambda_G + \lambda_H^2 < 1. This bound implies the spectral gap of the product is at least \min(\text{gap}_G, \text{gap}_H / e), up to constants, allowing iterative application to build constant-degree expander families of arbitrary size from small base expanders like Ramanujan graphs.^[18] The proof of expansion preservation analyzes the second-largest eigenvalue of the product's normalized adjacency matrix by decomposing an arbitrary eigenvector into components uniform and non-uniform across the n "clouds" (copies of H attached to each v \in V(G)). For uniform components, the jump step in G expands them using \lambda_G; for non-uniform components, the two steps in H expand them using \lambda_H, with the bound \lambda_G + \lambda_H^2 arising from coupling these effects via linear algebra on the restricted operators. This "cloud expansion" argument shows the product inherits and amplifies the mixing properties of its inputs.^[18]

Graph Lifts

In graph theory, a k-lift of a base graph B = (V_B, E_B) is a graph \tilde{B} = (V_{\tilde{B}}, E_{\tilde{B}}) equipped with a surjective covering map \pi: V_{\tilde{B}} \to V_B that is k-to-1, such that for every vertex v' \in \pi^{-1}(v) in the lift, its neighbors in \tilde{B} project exactly once to each neighbor of v in B.^[19] These lifts can be constructed systematically using voltage graphs, where edges of B are assigned elements (voltages) from a finite group \Gamma, and the lift \tilde{B} is derived as the covering graph whose vertices are pairs (v, g) with g \in \Gamma, and edges determined by the voltage assignments to ensure the covering property. This framework allows for controlled enlargement of the graph while preserving structural relations from the base. Random lifts of expander graphs inherit and often amplify the expansion properties of the base graph. Specifically, if the base graph B is a d-regular expander with second-largest eigenvalue \lambda, a random n-lift \tilde{B} has nontrivial eigenvalues bounded by O((\lambda \lor 2\sqrt{d-1}) \log(2\sqrt{d-1})) with high probability, leading to an improved spectral gap relative to the base.^[20] The spectral gap in such lifts can be analyzed through the voltage graph representation, where the eigenvalues of the lift's adjacency matrix are intertwined with those of the base via the group's representation theory, ensuring that random voltage assignments yield graphs with expansion close to the Ramanujan bound $2\sqrt{d-1}.^[20] Friedman's theorem establishes that almost all lifts of d-regular graphs (d \geq 3) are Ramanujan expanders, meaning their second-largest absolute eigenvalue is at most $2\sqrt{d-1} + \epsilon for any fixed \epsilon > 0, with the probability approaching 1 as the number of vertices grows. This result, conjectured earlier and fully resolved in 2008, implies that random lifts provide a probabilistic construction of optimal spectral expanders, where the spectral gap achieves the Alon-Boppana lower bound up to negligible error. For explicit constructions, Bilu and Linial introduced a deterministic method in 2006 using iterative 2-lifts—binary coverings where each vertex doubles into a pair connected based on edge signs—to build infinite families of d-regular expanders starting from small base graphs like the complete graph K_{d+1}.^[21] Each 2-lift step controls the new eigenvalues to lie within O(\sqrt{d} \log^3 d), yielding graphs with near-Ramanujan spectral gaps after a logarithmic number of iterations, and the process can be derandomized using discrepancy minimization to ensure the lifts are explicitly computable.^[21] This approach demonstrates how lifts can systematically amplify expansion without relying on probabilistic arguments, though randomized lifts guarantee existence for broader parameters.^[20]

Randomized Constructions

Randomized constructions of expander graphs employ probabilistic techniques to establish the existence of graphs with desirable expansion properties, without constructing them explicitly. These methods typically involve generating random graphs from a suitable probability distribution and showing that, with high probability (w.h.p.), the resulting graph satisfies expansion criteria. A foundational result in this domain is Pinsker's 1973 theorem, which demonstrates that a random d-regular graph on n vertices, sampled via the configuration model, has Cheeger constant h(G) \geq \frac{d-2}{2 \log d} w.h.p. as n \to \infty.^[1] In the spectral setting, randomized constructions yield graphs with bounded second-largest eigenvalue \lambda_2. Basic probabilistic arguments establish that a random d-regular graph satisfies \lambda_2 \leq d - \Omega(\sqrt{d}) w.h.p., providing a nontrivial spectral gap. This bound was strengthened by Friedman's theorem, which proves that random d-regular graphs are Ramanujan w.h.p., meaning \lambda_2 \leq 2\sqrt{d-1} for fixed d \geq 3 and large n. The configuration model serves as the primary algorithmic tool for these randomized constructions. It generates a random d-regular multigraph by pairing dn stubs (half-edges) uniformly at random and then simplifying to a simple graph, often using Markov chain Monte Carlo (MCMC) methods to sample from the space of d-regular graphs. These algorithms can be derandomized efficiently using the method of conditional expectations, which iteratively fixes random choices to preserve the probability of good expansion properties while reducing randomness.^[1] Randomized methods extend beyond regular graphs to establish the existence of vertex expanders for arbitrary degree sequences. For any graphical degree sequence with minimum degree at least \delta and maximum degree at most d, the generalized configuration model produces a graph that is a (\beta n, \gamma \delta)-vertex expander w.h.p. for suitable \beta, \gamma > 0, implying that expanders exist realizing any such degree sequence.^[1]

Recent Explicit Constructions

In recent years, significant progress has been made in constructing explicit expander graphs with strong vertex expansion properties, surpassing previous limitations tied to spectral expansion. In 2025, Hsieh, Lin, Mohanty, O'Donnell, and Zhang introduced the first explicit family of two-sided vertex expanders that bypass the spectral barrier.^[22] These constructions yield infinite families of d-regular graphs, for sufficiently large d, where every small vertex set S (of size up to roughly |V|^{1/2}) expands to approximately $0.6d|S|

distinct neighbors, improving upon the &#36;0.5d|S|

bound achieved by Ramanujan graphs.^[22] The method relies on a tripartite line product framework incorporating a 4-dimensional Ramanujan clique complex, combined with new bounds on triangle densities in such complexes.^[22] They also extend this to (d_1, d_2)-biregular bipartite graphs, achieving similar expansion factors of approximately $0.6d_1 from the left and $0.6d_2 from the right for small sets.^[22] Another breakthrough in 2025 came from Hsieh, Lubotzky, Mohanty, Reiner, and Zhang, who provided the first explicit construction of constant-degree lossless vertex expanders.^[3] For any \varepsilon > 0 and sufficiently large degree d, their d-regular graphs ensure that every small vertex set S (of size at most |V|^\alpha for some \alpha < 1) has at least (1 - \varepsilon)d|S| neighbors, implying at least (1 - 2\varepsilon)d|S| unique neighbors.^[3] This resolves a longstanding open problem originating from the work of Sipser and Spielman.^[3] The graphs are built via a careful product of a constant-sized lossless expander with a base graph derived from Ramanujan Cayley cubical complexes, and crucially, they admit a free group action.^[3] This free group action realizes new families of quantum low-density parity-check codes proposed by Lin and Hsieh with linear-time decoding complexity.^[3] In parallel, Lew, Nevo, Peled, and Raz developed the concept of rigidity expander graphs in 2025, generalizing traditional spectral expansion through connections to graph rigidity theory.^[23] Building on the d-dimensional algebraic connectivity a_d(G) introduced by Jordán and Tanigawa, which quantifies a graph's resistance to d-dimensional deformations, they define a family \{G_i\} as d-rigidity expanders if a_d(G_i) \geq \varepsilon > 0 for all i.^[24]^[23] Their main result establishes infinite families of k-regular d-rigidity expander graphs for k \geq 2d + 1, using edge subdivisions of 3-regular bipartite expander graphs to ensure robust connectivity across d-partite subgraphs.^[23] This ties expansion directly to rigidity properties, such as maintaining d-dimensional rigidity after vertex removals, with a_d(G) providing a quantitative measure.^[23]^[24] These advances also include deterministic explicit constructions that outperform the zig-zag product in specific parameter regimes for vertex expansion. For instance, the product-based methods in the lossless constructions achieve near-optimal unique-neighbor expansion with polynomial-time explicitness, exceeding zig-zag's guarantees for small sets in high-degree regimes without relying on randomization.^[3] Vertex expansion, which measures the growth of small sets to their neighborhoods, underpins these improvements by focusing on combinatorial rather than spectral metrics alone.^[22]

Key Properties

Expander Mixing Lemma

The expander mixing lemma provides a spectral bound on the uniformity of edge distribution in regular expander graphs. For a d-regular graph G=(V,E) on n vertices with adjacency eigenvalues \lambda_1 = d \geq \lambda_2 \geq \cdots \geq \lambda_n, let \lambda = \max\{|\lambda_2|, |\lambda_n|\}. Then, for any subsets A, B \subseteq V,

\left| |E(A,B)| - \frac{d |A| |B|}{n} \right| \leq \lambda \sqrt{ |A| |B| \left(1 - \frac{|A|}{n}\right) \left(1 - \frac{|B|}{n}\right) }.

This inequality, first established by Alon and Chung, quantifies how closely the number of edges between A and B approximates the expectation in a random d-regular graph, with the error controlled by the spectral parameter \lambda. Smaller \lambda implies stronger uniformity, a hallmark of expander graphs.^[1] The proof proceeds via the spectral decomposition of the adjacency matrix A. Let \mathbf{1}_A and \mathbf{1}_B denote the indicator vectors of A and B. The number of edges |E(A,B)| equals \mathbf{1}_A^T A \mathbf{1}_B. Expand \mathbf{1}_A and \mathbf{1}_B in the orthonormal eigenvector basis \{\mathbf{v}_i\}_{i=1}^n of A, where A \mathbf{v}_i = \lambda_i \mathbf{v}_i and \mathbf{v}_1 = \mathbf{1}/\sqrt{n}. The inner product \mathbf{1}_A^T A \mathbf{1}_B = \sum_{i=1}^n \lambda_i \langle \mathbf{1}_A, \mathbf{v}_i \rangle \langle \mathbf{1}_B, \mathbf{v}_i \rangle. The i=1 term yields the expected value (d/n) |A| |B| = d \langle \mathbf{1}_A, \mathbf{v}_1 \rangle \langle \mathbf{1}_B, \mathbf{v}_1 \rangle. For i \geq 2, bound the sum by \lambda \sum_{i=2}^n |\langle \mathbf{1}_A, \mathbf{v}_i \rangle| \cdot |\langle \mathbf{1}_B, \mathbf{v}_i \rangle| and apply the Cauchy-Schwarz inequality: \left( \sum_{i=2}^n |\langle \mathbf{1}_A, \mathbf{v}_i \rangle| \cdot |\langle \mathbf{1}_B, \mathbf{v}_i \rangle| \right)^2 \leq \left( \sum_{i=2}^n \langle \mathbf{1}_A, \mathbf{v}_i \rangle^2 \right) \left( \sum_{i=2}^n \langle \mathbf{1}_B, \mathbf{v}_i \rangle^2 \right). The sums equal \| \mathbf{1}_A - \langle \mathbf{1}_A, \mathbf{v}_1 \rangle \mathbf{v}_1 \|^2 = |A| (1 - |A|/n) and analogously for B, yielding the error term.^[1] This lemma implies that expander graphs exhibit quasi-random behavior: edges are nearly uniformly distributed, mimicking a random model despite sparsity. For instance, if A is a large independent set (so E(A,A)=0), the bound forces |A| = O(n \lambda / d + \sqrt{n \lambda / d}) or smaller, limiting the size of independent sets in good expanders. It also ensures few edges between disjoint sets deviating from the random expectation, aiding analyses in discrepancy and pseudorandomness.^[1] A bipartite analogue holds for balanced d-regular bipartite graphs G=(L \cup R, E) with |L|=|R|=n, and singular values \sigma_1 = d \geq \sigma_2 \geq \cdots \geq \sigma_n of the biadjacency matrix, letting \lambda = \max\{ \sigma_2, |\sigma_n| \}. For A \subseteq L, B \subseteq R,

\left| |E(A,B)| - \frac{d |A| |B|}{n} \right| \leq \lambda \sqrt{ |A| (n - |A|) \cdot \frac{|B|}{n} \left(1 - \frac{|B|}{n}\right) },

this version, useful for expanders in coding and sampling, follows a similar spectral proof using the biadjacency singular vectors and Cauchy-Schwarz. For unbalanced cases (|L| \neq |R|), the largest singular value is d \sqrt{|L|/|R|}, and the bound adjusts accordingly using relative spectral gap.^[1]

Expander Walks

A random walk on an expander graph is generated by starting at an arbitrary vertex and repeatedly selecting a uniform random neighbor at each step. This process defines a Markov chain whose transition matrix is the normalized adjacency matrix, with the uniform distribution over vertices serving as the stationary distribution. Due to the strong connectivity of expander graphs, such walks rapidly explore the graph, making them useful for derandomization and sampling tasks.^[1] The mixing time of a random walk on a d-regular n-vertex expander graph with second-largest adjacency eigenvalue \lambda_2 is \tau = O\left( \frac{d \log (n / \varepsilon)}{d - \lambda_2} \right) steps to reach \varepsilon-closeness in total variation distance to the stationary uniform distribution. This bound arises from the spectral gap of the graph, which governs the exponential decay of the distance to uniformity; specifically, the second eigenvalue of the transition matrix is \lambda_2 / d < 1, leading to convergence in O\left( \frac{\log (n / \varepsilon)}{1 - \lambda_2 / d} \right) steps. For constant degree d and bounded \lambda_2 / d, this ensures polylogarithmic mixing regardless of n.^[1]^[15] Expander walks exhibit a unique neighbor property, where short paths of length up to polylogarithmic in n are collision-free (i.e., visit distinct vertices) with high probability, provided the graph has strong vertex expansion. This follows from the fact that small sets expand to nearly d times their size in unique neighbors, minimizing the chance of revisiting vertices early in the walk. Such collision-free paths are essential for using expander walks to construct extractors, as they generate nearly uniform and independent outputs from limited randomness, approximating the behavior of truly random samples without overlaps.^[1] Zig-zag walks, defined via the zig-zag graph product, enable space-efficient derandomization by composing walks on two expander graphs: a three-step process consisting of a step on the base graph G, followed by two steps on a small expander H attached to each vertex of G. This construction preserves expansion while reducing the space required to simulate the walk, allowing deterministic logarithmic-space algorithms to mimic probabilistic ones on expanders. The resulting graph remains an expander with second eigenvalue bounded by a function of the inputs' gaps, facilitating applications like proving SL = L in complexity theory.^[1]

Spectral Gap Implications

The spectral gap d - \lambda_2 of a d-regular expander graph, where \lambda_2 is the second-largest eigenvalue of the adjacency matrix, fundamentally influences the graph's cut properties and connectivity. In particular, it provides a lower bound on the Cheeger constant h(G) = \min_{|S| \leq n/2} \frac{|E(S, V \setminus S)|}{|S|}, with h(G) \geq \frac{d - \lambda_2}{2}.^[25] This relation ensures that minimum cuts are bounded below by the spectral gap, as h(G) quantifies the smallest relative expansion across balanced partitions, preventing bottlenecks in the graph structure.^[25] The Cheeger inequalities elaborate on this connection between spectral and combinatorial expansion (detailed in Cheeger Inequalities). A direct structural implication is uniform expansion across all vertex subsets: for every S \subseteq V, the edge boundary satisfies |E(S, V \setminus S)| \geq \frac{d - \lambda_2}{2} |S|.^[25] This inequality, derived from the expander mixing lemma and eigenvalue bounds, guarantees that no subset is poorly connected to the rest of the graph, enhancing overall uniformity in neighborhood growth.^[25] The spectral gap also defines the conductance \phi(G) = \frac{d - \lambda_2}{2d}, a dimensionless measure that normalizes expansion relative to the degree.^[25] This links discrete graph theory to continuous settings, such as the Cheeger constant in Riemannian manifolds, where \phi(G) captures the graph's ability to avoid small cuts efficiently.^[25] These expansion guarantees confer robustness to perturbations: the spectral gap is preserved, and the graph maintains strong connectivity, under up to \Omega\left(n \frac{d - \lambda_2}{d}\right) edge or vertex failures.^[25] This tolerance arises because the relative expansion \frac{d - \lambda_2}{d} allows a proportional fraction of the graph to fail without collapsing cuts or isolating components.^[25]

Applications

Algorithms and Complexity Theory

Expander graphs have played a pivotal role in advancing parallel algorithms and complexity theory, particularly in constructing efficient sorting networks and resolving key questions about space-bounded computation.^[1] The seminal Ajtai–Komlós–Szemerédi (AKS) sorting network from 1983 leverages expander graphs to build ε-halvers, which are comparator networks that approximately balance the number of elements routed to each output. These halvers enable a recursive construction of a sorting network with depth O(log n) and size O(n log n), demonstrating that sorting can be performed efficiently in the parallel complexity class NC. This breakthrough resolved a major open problem in parallel computation by showing that sorting is possible with polylogarithmic depth using a polynomial number of comparators.^[26] In complexity theory, expander graphs were instrumental in Omer Reingold's 2005 proof that the complexity class SL equals L. Reingold's algorithm solves undirected s-t connectivity in logarithmic space by transforming arbitrary connected graphs into expanders using the zig-zag graph product, which preserves expansion while allowing efficient traversal. This enables a deterministic logspace universal traversal sequence that explores the graph's structure without exceeding space bounds, collapsing the symmetric logspace class into deterministic logspace and marking a landmark result in space complexity.^[27] Expander graphs also facilitate the construction of approximate shortest path spanners, as shown in the work of Thorup and Zwick in 2001. Their approach builds (2k-1)-spanners—subgraphs preserving distances up to a multiplicative factor of 2k-1—with O(n^{1+1/k}) edges by sampling vertex clusters that exhibit expander-like connectivity properties, ensuring low stretch while maintaining sparsity. This has implications for parallel algorithms by allowing efficient preprocessing and querying of distances in undirected weighted graphs.^[28] Furthermore, expander graphs contribute to parallel derandomization by reducing the randomness required in NC algorithms. Techniques such as expander walks generate pseudorandom sequences that fool probabilistic parallel computations, enabling deterministic simulations within NC while preserving efficiency. For instance, random walks on expanders can derandomize error amplification in randomized parallel algorithms, replacing high-randomness sources with expander-based generators that require only polylogarithmic seeds. This approach has been applied to parallelize procedures like matching and connectivity testing, broadening the scope of derandomized parallel computation.^[1]

Coding Theory

Expander graphs have played a pivotal role in the development of error-correcting codes, particularly in constructing low-density parity-check (LDPC) codes with efficient decoding algorithms. In the 1980s, R. Michael Tanner introduced a recursive construction of codes based on bipartite graphs, where bits are placed on edges and local constraints are enforced by short codes at vertices. These Tanner codes, when built using expander graphs, yield LDPC codes that support linear-time decoding algorithms capable of correcting errors up to a constant fraction of the code's capacity, making them suitable for practical applications requiring low complexity. Building on this foundation, Michael Sipser and Daniel A. Spielman in 1996 developed expander codes, a specific class of Tanner codes utilizing bipartite expander graphs with right-degree regularity.^[29] The key innovation lies in the unique neighbor expansion property of these graphs: for any set of at most αn vertices on the left side, where α is a small constant, the number of unique neighbors on the right exceeds a multiple of the set size.^[29] This property enables linear-time sequential decoding algorithms that uniquely recover the codeword from erasures or errors up to a fraction of the minimum distance, and it extends to list-decodable codes by producing short lists of candidate codewords.^[29] In quantum coding theory, expander graphs facilitate the construction of quantum LDPC (qLDPC) codes with desirable properties. In 2022, Ting-Chun Lin and Min-Hsiu Hsieh proposed qLDPC codes derived from balanced products of lossless expander graphs, achieving constant encoding rate, linear minimum distance, and linear-time decoding under erasure noise, assuming the existence of suitable lossless expanders.^[30] Recent explicit constructions of lossless vertex expanders in 2025 realize these codes deterministically, confirming their constant rate and linear distance while preserving efficient decoding, thus advancing fault-tolerant quantum computing.^[3] Expander graphs also connect to polar codes through generalizations of the channel polarization process. High-girth matrices, which exhibit expander-like spectral properties, serve as kernels in polar code constructions to accelerate polarization and improve rates or list-decoding performance beyond the standard binary kernel.

Pseudorandomness and Sampling

Expander graphs play a central role in pseudorandomness by enabling the construction of seeded randomness extractors from weak sources of randomness. A left-regular bipartite expander graph G with left side of size n, right side of size m, degree d, and spectral expansion parameter \lambda < 1 - \delta for some constant \delta > 0 can be viewed as a seeded extractor \text{Ext}: \{0,1\}^n \times \{0,1\}^{\log d} \to \{0,1\}^{\log m}. For an input source X with min-entropy at least k \geq \log_2 m + \log(1/\epsilon) + O(\log(1/\delta)), the output distribution \text{Ext}(X, U_{\log d}) is \epsilon-close in total variation distance to the uniform distribution over \{0,1\}^{\log m}, where U_{\log d} is the uniform seed. This construction leverages the expansion property to ensure that even biased or correlated inputs produce nearly uniform outputs, with the seed length \log d = O(\log(n/k)) being efficient. Seminal work established explicit constructions of such unbalanced expanders with near-optimal parameters, supporting applications in derandomization and cryptography.^[31]^[1] Expander walk sampling provides an efficient method for generating approximate uniform samples over the vertex set of a graph. In a d-regular expander G on n vertices with second-largest eigenvalue \lambda, a random walk of length t = O\left( \frac{\log(n/\epsilon)}{1 - \lambda} \right) started from any initial vertex produces a distribution that is \epsilon-close in total variation distance to the uniform distribution \pi over the vertices. This mixing time bound arises from the spectral gap $1 - \lambda, ensuring rapid convergence regardless of the starting point. For constant expansion (fixed \lambda < 1), the number of steps simplifies to O(\log(n/\epsilon)), allowing \epsilon-approximate uniform samples with O(\log n) randomness per sample when \epsilon is polynomial in $1/n. This technique is particularly useful for derandomizing algorithms that require uniform sampling, such as Monte Carlo methods, and extends to approximating expectations of functions over the graph with high probability using multiple short walks.^[15]^[1] The expander mixing lemma further demonstrates how expanders generate pseudorandom objects that fool certain graph-theoretic tests, including those based on subgraph counts. For a d-regular expander G on n vertices with \lambda(G) \leq \lambda, the lemma states that for any subsets S, T \subseteq V(G), the number of edges between S and T satisfies |e(S,T) - \frac{d |S| |T|}{n}| \leq \lambda \sqrt{|S| |T|}. This bound implies that G behaves like a random graph in terms of edge distributions, and by extension, the expected number of induced copies of small fixed subgraphs H in G is close to that in the Erdős–Rényi model G(n, d/n), up to an error factor depending on \lambda^{|E(H)|}. Consequently, expanders fool subgraph density tests with advantage at most poly(\lambda), making them quasirandom graphs suitable for hardness amplification in property testing. This property has been pivotal in constructing pseudorandom graph families for algorithmic derandomization.^[15]^[1] Expander graphs underpin Nisan's pseudorandom generators (PRGs) for space-bounded derandomization, enabling the simulation of randomized log-space computations deterministically. In the Impagliazzo–Nisan–Wigderson (INW) construction, an expander graph is used to generate a pseudorandom string that fools space-s(n) branching programs or Turing machines, stretching a seed of length O(s \log n) to output length n^{O(1)} while preserving the acceptance probability up to $1/\text{poly}(n). The generator relies on the expander's mixing properties to ensure that the pseudorandom walk on the computation's dependency graph mimics true randomness, avoiding dependencies that space-bounded machines could exploit. This approach yields unconditional derandomization results, such as placing RL in DSPACE(O(\log^2 n)), and has been refined with explicit expander constructions like the zig-zag product to achieve near-optimal seed lengths.^[1]

Machine Learning and AI

Expander graphs have emerged as a key tool in modern machine learning and artificial intelligence, particularly for enhancing scalability and efficiency in neural architectures handling large-scale graph data and large language models (LLMs). Their strong expansion properties enable sparse yet well-connected structures, which mitigate computational bottlenecks in attention mechanisms and parameter optimization while preserving model performance. Recent advancements in the 2020s leverage these graphs to address challenges in graph neural networks (GNNs) and transformer-based models, allowing training on datasets with millions of nodes without quadratic complexity overheads.^[32] One prominent application is the Exphormer framework, which integrates expander graphs into sparse attention mechanisms for graph transformers. By overlaying expander graphs on input graphs alongside virtual global nodes, Exphormer achieves linear-time complexity O(|V| + |E|) for attention computation, where |V| is the number of vertices and |E| the number of edges, enabling scalability to graphs with over a million nodes. This approach outperforms dense transformers and other sparse variants on benchmarks like molecular property prediction and graph classification tasks, demonstrating up to 10x speedups in training time while maintaining or exceeding accuracy. For instance, on the ogbn-arxiv dataset, Exphormer variants achieve test accuracies of 72.4% with significantly reduced memory usage compared to full attention baselines.^[33] In the context of LLMs, expander-adapted low-rank adaptation (LoRA) methods like XoRA utilize expander graphs for efficient fine-tuning by sparsifying adapter matrices. XoRA applies masks derived from Ramanujan expander graphs to LoRA parameters, ensuring high edge connectivity at sparsity levels exceeding 90%, which prunes parameters while preserving information flow through the graph structure. This results in comparable performance to standard LoRA on downstream tasks such as those in the GLUE benchmark (e.g., natural language inference), but with up to 96.9% fewer trainable parameters, as evaluated on models like LLaMA-7B. The expander-based pruning maintains model robustness by avoiding bottlenecks in the adaptation graph, facilitating deployment on resource-constrained hardware.^[34]^[35] Building on structured pruning techniques, the EGGS-PTP method employs expander graphs to guide post-training compression of LLMs, focusing on N:M sparsity patterns. By modeling the pruning process as an expander-guided sparsification, EGGS-PTP identifies critical parameter subsets that retain the spectral properties of the original model, reducing overall complexity from O(n^2) to near-linear while preserving performance on benchmarks like GLUE and SuperGLUE. Experiments on LLaMA models show perplexity increases of up to 47% after 4:8 pruning (activating 4 out of every 8 parameters) on the WikiText2 dataset (e.g., from 5.47 to 8.04 for LLaMA2-7B), with up to 2x inference speedup and 50% memory savings, highlighting the role of expander connectivity in maintaining equitable parameter importance across layers.^[36] Expander graphs also play a crucial role in graph diffusion models within GNNs, particularly for equitable neighbor sampling during message passing. In diffusion-based GNN frameworks, expanders facilitate balanced propagation by ensuring rapid mixing and uniform coverage of neighborhoods, which prevents oversampling of high-degree nodes and promotes fair representation learning. For example, expander graph propagation overlays provide a sparse diffusion operator that approximates continuous-time diffusion processes with O(n cost, improving generalization on heterogeneous graphs like social networks, where standard random walks may introduce bias. This has been shown to improve ROC-AUC by approximately 5% relatively (e.g., from 0.7558 to 0.7934 on ogbn-molhiv) compared to vanilla GNN samplers.^[37]

Other Domains

Expander graphs have found applications in voting and consensus protocols, where their strong connectivity properties enable rapid agreement among participants. In quasi-majority functional voting models, agents on the vertices of an expander graph update their opinions synchronously based on a threshold function of neighbors' votes, leading to consensus in logarithmic time relative to the graph size. Specifically, for n-vertex expander graphs, the expected consensus time is bounded by O(log n) rounds, leveraging a nonlinear extension of the expander mixing lemma to control opinion variance and drift toward uniformity.^[38] In rigidity theory, expander graphs provide a framework for analyzing the structural flexibility of frameworks in higher dimensions. Rigidity expanders generalize spectral expansion through the d-dimensional algebraic connectivity a_d(G), which quantifies a graph's resistance to infinitesimal flexes—motions that preserve edge lengths to first order—via the kernel of the rigidity matrix. This measure links graph flexibility directly to expansion: strong spectral expansion in subgraphs from a d-partition implies a positive lower bound on a_d(G), ensuring the graph is generically d-rigid for sufficiently high degree, as in k-regular graphs with k \geq 2d+1. Such constructions yield infinite families of rigidity expanders, contrasting flexible graphs where poor expansion allows non-trivial flexes.^[23] In physics, expander graphs serve as models for disordered systems, capturing the interplay between sparsity and robust propagation in random environments. For instance, k-regular random graphs, which exhibit expander properties, model disordered lattices in studies of coherent states and localization; their expansion ensures large-scale coherence despite local disorder, as seen in quantum walks where the spectral gap prevents localization tails.^[39] Similarly, in Anderson localization on random regular graphs, expanders approximate infinite-dimensional disordered systems, revealing a mobility edge where expansion influences delocalization transitions under renormalization group flows.^[40] Expander graphs also model robust connectivity in social networks, particularly sparse communities where traditional dense structures fail. Large-scale analyses of platforms like Facebook and Twitter reveal that their graphs exhibit expander-like expansion factors despite average degrees below 50, ensuring short paths and resilience to node failures in community formation.^[41] In geometric inhomogeneous random graph models of social networks, latent space embeddings yield expanders when connection probabilities favor local ties, promoting robust global mixing in sparse regimes and explaining observed small-world properties without dense cliques.^[42]

References

[1]
[PDF] Expander graphs and their applications - CS - Huji
Aug 7, 2006 · SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON. An Overview. A major consideration we had in writing this survey was to make it accessible to ...
[2]
https://ieeexplore.ieee.org/document/1057683
[3]
https://arxiv.org/abs/2504.15087
[4]
254B, Notes 1: Basic theory of expander graphs - Terry Tao
Dec 2, 2011 · The objective of this course is to present a number of recent constructions of expander graphs, which are a type of sparse but “pseudorandom” graph of ...
[5]
On the complexity of a concentrator | Semantic Scholar
In this paper a swi tcbing network with n inputs and m outputs is considered. The network satisfies the following condition: any k ~ m inputs can be ...
[6]
G. A. Margulis, “Explicit Constructions of Concentrators”, Probl ...
The theory of group representations is used to solve the problems of the explicit construction of concentrators. Received: 02.06.1972. Bibliographic databases:.
[7]
Ramanujan graphs | Combinatorica
Aug 5, 1987 · Lubotzky, R. Phillips, P. Sarnak, Ramanujan conjecture and explicit construction of expanders,Proc. Stoc. 86 (1986), 240–246. Google ...
[8]
[PDF] Entropy Waves, the Zig-Zag Graph Product, and New Constant ...
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders. Author(s): Omer Reingold, Salil Vadhan, Avi Wigderson. Source: The Annals of ...
[9]
[2504.15087] Explicit Lossless Vertex Expanders - arXiv
Apr 21, 2025 · We give the first construction of explicit constant-degree lossless vertex expanders. Specifically, for any \varepsilon > 0 and sufficiently large d,
[10]
Rigidity Expander Graphs | Combinatorica
This paper studies a generalization of spectral graph expansion that was recently introduced by Jordán and Tanigawa via the theory of graph rigidity.
[11]
[PDF] Basic Facts about Expander Graphs
A strongly explicit construction of an infinite family of (d-regular) graphs {GN }N∈S is a polynomial-time algorithm that on input N ∈ S (in binary), a vertex ...
[12]
[PDF] Expander Graphs and their Applications - Boaz Barak
Jan 1, 2003 · We introduce the construction of Margulis for expander graphs which is in fact a continuous graph with an expansion property. We show an analogy ...
[13]
[PDF] New Explicit Constant-Degree Lossless Expanders
Jan 8, 2024 · A lossless expander is defined as a graph for which for all sufficiently small vertex sets, most of the outgoing edges lead to distinct ...
[14]
λ 1 , Isoperimetric inequalities for graphs, and superconcentrators
A general method for obtaining asymptotic isoperimetric inequalities for families of graphs is developed. Some of these inequalities have been applied to ...
[15]
[PDF] Bounds on existence of odd and unique expanders
We start this section by listing two simple lemmas relating vertex-expanders with edge-expanders. Both expansion types imply that the graph is an expander in.
[16]
[PDF] Expander Graphs - Harvard SEAS
For graphs with a constant fraction of self-loops at each vertex, the theorem implies that the edge expansion is bounded away from 0 iff the spectral expansion ...Missing: origins | Show results with:origins
[17]
[PDF] An Elementary Construction of Constant-Degree Expanders
Abstract. We describe a short and easy to analyze construction of constant-degree expanders. The construction relies on the replacement product, applied by ...
[18]
[PDF] Entropy Waves, The Zig-Zag Graph Product, and New Constant ...
Aug 1, 2001 · Abstract. The main contribution of this work is a new type of graph product, which we call the zig-zag product. Taking a product of a large ...Missing: 2002 | Show results with:2002
[19]
Constructing expander graphs by 2-lifts and discrepancy vs. spectral ...
Apr 8, 2004 · We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations.
[20]
[PDF] Spectra of lifted Ramanujan graphs.
In particular, it implies that a typical n-lift of a Ramanujan graph is nearly Ramanujan.
[21]
Lifts, Discrepancy and Nearly Optimal Spectral Gap* | Combinatorica
Jan 6, 2005 · We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations.
[22]
Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
Nov 18, 2024 · We construct the first explicit two-sided vertex expanders that bypass the spectral barrier. Previously, the strongest known explicit vertex ...Missing: Cohen- Ellenberg 2025
[23]
[2304.01306] Rigidity expander graphs - arXiv
Apr 3, 2023 · This is a quantitative measure of the d-dimensional rigidity of G which generalizes the well-studied notion of spectral expansion of graphs.Missing: 2025 | Show results with:2025
[24]
On the $d$-dimensional algebraic connectivity of graphs - arXiv
May 11, 2022 · The d-dimensional algebraic connectivity a_d(G) of a graph G=(V,E), introduced by Jordán and Tanigawa, is a quantitative measure of the d-dimensional rigidity ...
[25]
[PDF] Expander graphs and their applications - CS - Huji
Aug 7, 2006 · EXPANDER GRAPHS AND THEIR APPLICATIONS. 441. We are also grateful for ... SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON. 3.46. 3.465 n ...
[26]
Sorting inc logn parallel steps | Combinatorica
Ajtai,; J. Komlós &; E. Szemerédi. 559 Accesses. 447 Citations. 6 Altmetric. Explore all metrics. Abstract. We give a sorting network withcn logn comparisons.
[27]
[PDF] Undirected Connectivity in Log-Space∗ - Omer Reingold
Here we transform any connected graph (which is already large but is not an expander) into an expander. On a technical level, this means that the zig-zag ...
[28]
Approximate distance oracles | Proceedings of the thirty-third annual ...
Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse spanners of weighted graphs, and ...
[29]
https://ieeexplore.ieee.org/document/556667
[30]
Good quantum LDPC codes with linear time decoder from lossless ...
Mar 7, 2022 · We study qLDPC codes constructed from balanced products and lossless expanders. We found that assuming the existence of 2-sided lossless expander graphs with ...Missing: 2025 | Show results with:2025
[31]
[PDF] Unbalanced Expanders and Randomness Extractors from ...
We give an improved explicit construction of highly un- balanced bipartite expander graphs with expansion arbi- trarily close to the degree (which is ...
[32]
Exphormer: Scaling transformers for graph-structured data
Jan 23, 2024 · In this post, we have presented Exphormer, a sparse attention framework that uses expander graphs to improve scalability of graph transformers.
[33]
[2303.06147] Exphormer: Sparse Transformers for Graphs - arXiv
Mar 10, 2023 · In this paper, we introduce Exphormer, a framework for building powerful and scalable graph transformers. Exphormer consists of a sparse ...
[34]
XoRA: Expander adapted LoRA finetuning - OpenReview
Feb 4, 2025 · Parameter-efficient fine-tuning aims to reduce the computational cost of adapting foundational models to downstream tasks.Missing: LLM structure pruning
[35]
[PDF] XORA: EXPANDER ADAPTED LORA FINETUNING - OpenReview
Parameter-efficient fine-tuning aims to reduce the computational cost of adapt- ing foundational models to downstream tasks.
[36]
https://arxiv.org/abs/2508.09471
[37]
[2210.02997] Expander Graph Propagation - arXiv
Oct 6, 2022 · In this work, we propose an elegant approach based on propagating information over expander graphs. We leverage an efficient method for ...Missing: equitable sampling diffusion
[38]
https://doi.org/10.1002/rsa.21224
[39]
Large Coherent States Formed from Disordered k-Regular Random ...
Nov 6, 2023 · The analysis considers the possible role of the expander property of k-regular random graphs. Keywords: coherence; expander graph; quantum ...
[40]
Renormalization group analysis of the Anderson model on random ...
A particle in quantum mechanics can escape thermalization in the presence of a random potential, a phenomenon known as Anderson localization.
[41]
[PDF] Expansion Properties of Large Social Graphs - LIX
In this paper, we study the expansibility of large social graphs, a structural property based on the notion of expander graphs (i.e. sparse graphs with strong ...
[42]
https://arxiv.org/abs/2506.19485