Fact-checked by Grok 2 weeks ago

Ramanujan graph

A Ramanujan graph is a d-regular graph whose adjacency matrix has its second-largest eigenvalue in absolute value at most $2\sqrt{d-1}, achieving the optimal bound for spectral expanders as established by the Alon-Boppana theorem.^[1] This bound ensures that Ramanujan graphs exhibit near-ideal expansion properties, meaning small sets of vertices connect efficiently to the rest of the graph, with the trivial largest eigenvalue equal to d and all others bounded tightly.^[1] The concept was introduced in 1988 by Alexander Lubotzky, Ronen Phillips, and Peter Sarnak, who coined the term in honor of Srinivasa Ramanujan due to the role of the Ramanujan-Petersson conjecture in proving the spectral properties of their constructions. These original Lubotzky-Phillips-Sarnak (LPS) graphs are explicit families of (p+1)-regular Ramanujan graphs for primes p \equiv 1 \pmod{4}, constructed as Cayley graphs of \mathrm{[PSL](/page/PSL)}(2, q) over finite fields using specific symmetric generating sets derived from quaternion algebras.^[1] For instance, the graph X_{5,29} is a 6-regular Ramanujan graph on 12,180 vertices.^[1] Ramanujan graphs are the strongest known explicit expanders, surpassing random regular graphs in spectral gap while matching the theoretical optimum, and they play crucial roles in computer science applications such as error-correcting codes, derandomization, and network design.^[1] In 2013, Adam Marcus, Daniel Spielman, and Nikhil Srivastava resolved a long-standing open problem by proving the existence of bipartite Ramanujan graphs of every degree d > 2 using interlacing families (published in the Annals of Mathematics in 2015).^[1] Bipartite variants, including those with right-degree d and left-degree k, further extend their utility in matching problems and hashing.^[1] In 2020, explicit constructions of \epsilon-near-Ramanujan d-regular graphs were given for every d \geq 3 and \epsilon > 0.^[2] Ongoing research explores higher-dimensional analogues called Ramanujan complexes, which generalize these properties to simplicial structures.^[3]

Background on expander graphs

Spectral properties of graphs

In spectral graph theory, the adjacency matrix A of an undirected graph G = (V, E) with n = |V| vertices is an n \times n symmetric matrix where A_{ij} = 1 if there is an edge between vertices i and j, and A_{ij} = 0 otherwise (with zeros on the diagonal for simple graphs without loops).^[4] Since A is real symmetric, it is orthogonally diagonalizable, and its eigenvalues \lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n are real numbers.^[5] For a d-regular graph, where every vertex has degree d, the largest eigenvalue is \lambda_1 = d, with the all-ones vector as the corresponding eigenvector.^[6] The eigenvalues satisfy d = \lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n \geq -d, and the spectral gap is defined as \lambda_1 - \lambda_2, where \lambda_2 denotes the second-largest eigenvalue in absolute value (i.e., \max(|\lambda_2|, |\lambda_n|)).^[5] This gap quantifies the graph's connectivity and mixing properties, with larger gaps indicating better expansion behavior.^[4] The normalized Laplacian matrix, denoted \mathcal{L}, is given by \mathcal{L} = I - D^{-1/2} A D^{-1/2}, where D is the diagonal degree matrix and I is the identity matrix; for d-regular graphs, this simplifies to \mathcal{L} = I - \frac{1}{d} A.^[7] Its eigenvalues satisfy $0 = \mu_1 \leq \mu_2 \leq \dots \leq \mu_n \leq 2, and the second-smallest eigenvalue \mu_2 (the normalized spectral gap) relates to the graph's expansion via Cheeger's inequality: \frac{h(G)^2}{2} \leq \mu_2 \leq 2 h(G), where h(G) is the Cheeger constant measuring the minimum expansion of cuts.^[8] Expander graphs are characterized by large spectral gaps in this sense.^[9] Spectral graph theory originated in the mid-20th century, with foundational contributions by Miroslav Fiedler in the 1970s, particularly on the algebraic connectivity via the second-smallest Laplacian eigenvalue.

Definition and vertex expansion

Expander graphs are sparse yet highly connected structures in graph theory, characterized by their ability to ensure that small sets of vertices reach a disproportionately large number of neighbors. A d-regular graph G on n vertices is combinatorially defined as an (n,d,\alpha)-expander if, for every subset S \subseteq V(G) with |S| \leq n/2, the neighborhood N(S) satisfies |N(S)| \geq \alpha |S|, where \alpha > 1 is a fixed expansion parameter independent of n.^[10] This vertex expansion property quantifies how well the graph "expands" small sets, preventing bottlenecks in connectivity. The vertex expansion factor h_v(G) formalizes this as h_v(G) = \min_{S \subseteq V, |S| \leq n/2} |N(S)| / |S|, while the related edge expansion h_e(G) = \min_{S \subseteq V, |S| \leq n/2} |E(S, \overline{S})| / |S| measures the minimum number of edges leaving S per vertex in S, where E(S, \overline{S}) denotes the edge boundary.^[10]^[11] These combinatorial notions are intimately linked to the spectral properties of the graph's adjacency matrix, particularly the spectral gap d - \lambda_2, where \lambda_2 is the second-largest eigenvalue in absolute value. Cheeger's inequality provides a bridge between them: for a d-regular graph, \frac{d - \lambda_2}{2} \leq h(G) \leq \sqrt{2 d (d - \lambda_2)}, where h(G) denotes the (edge) expansion constant.^[10]^[12] This bidirectional bound shows that a large spectral gap implies strong combinatorial expansion (and vice versa, up to quadratic factors), making eigenvalues a computable proxy for expansion. For instance, poor expanders like the disjoint union of cliques exhibit minimal expansion: a set S entirely within one clique has |N(S)| = 0 outside its component, yielding h_v(G) \approx 0.^[13] In contrast, the complete graph K_n (with d = n-1) achieves near-optimal vertex expansion, as |N(S)| = n - |S| for any proper S, so h_v(G) \geq 1 when |S| \leq n/2.^[10] Expander graphs play a pivotal role in pseudorandomness and derandomization by mimicking the behavior of truly random graphs with far fewer edges, enabling efficient constructions of pseudorandom objects.^[10] Their expansion ensures rapid mixing of random walks, which underpins derandomization techniques such as error reduction in probabilistic algorithms and explicit constructions for problems like undirected s-t connectivity in logarithmic space.^[11] For example, expanders facilitate randomness-efficient sampling and hardness-of-approximation proofs in complexity theory, reducing reliance on unbounded randomness sources.^[10]

The Ramanujan bound

Alon-Boppana theorem

The Alon–Boppana theorem provides a fundamental lower bound on the largest absolute value of the nontrivial eigenvalues of the adjacency matrix of d-regular graphs, establishing an asymptotic limit that cannot be surpassed by any infinite family of such graphs as the number of vertices grows. Specifically, the theorem states that for any fixed integer d \geq 2 and any \varepsilon > 0, in any infinite family of d-regular graphs, \liminf_{n \to \infty} \max_{2 \leq i \leq n} |\lambda_i| \geq 2\sqrt{d-1} - \varepsilon. This bound highlights the inherent limitations on spectral expansion in regular graphs, showing that the nontrivial eigenvalues approach $2\sqrt{d-1} from below in the worst case for large n. The value $2\sqrt{d-1} arises as the spectral radius of the adjacency operator on the infinite d-regular tree, the universal cover of any d-regular graph. This serves as the optimal threshold for bounding the absolute values of nontrivial eigenvalues in graphs with ideal expansion properties, separating the largest eigenvalue d from the rest. The theorem originated in the 1980s through independent contributions by Noga Alon and Ravi Boppana, who built on early spectral graph theory and expander constructions from the 1970s, such as those by Pinsker and Margulis.^[14] Alon's work in 1986 connected eigenvalues to expander properties via combinatorial arguments, while Boppana's 1988 analysis refined the bound using index-theoretic methods on graph bisections. These results were later surveyed and contextualized in broader expander literature. A standard proof sketch employs the trace method, leveraging counts of closed walks to bound eigenvalues from below. Consider the adjacency matrix A of a d-regular graph G on n vertices. The trace \operatorname{tr}(A^{2\ell}) = \sum_{i=1}^n \lambda_i^{2\ell} counts the number of closed walks of length $2\ell in G. Since there are exactly nd^\ell closed walks of even length $2\ell that stay within distance \ell of a starting vertex (as in the local tree approximation), and the contribution from the largest eigenvalue d^{2\ell} is at most n d^{2\ell}, the remaining sum over nontrivial eigenvalues satisfies \sum_{i=2}^n \lambda_i^{2\ell} \geq nd^\ell (1 - O(\ell^2 / n)) for suitable \ell = o(\sqrt{n}). Dividing by n and taking \ell-th roots yields \max_{2 \leq i \leq n} |\lambda_i| \geq 2\sqrt{d-1} - o(1), implying the lower bound on the nontrivial eigenvalues for infinitely many graphs by considering sequences where the diameter grows slowly. Refinements by Nilli in 1991 sharpen the error term using more precise walk counts involving Catalan numbers in the d-regular tree. As a consequence, no infinite family of d-regular graphs can achieve a spectral gap larger than d - 2\sqrt{d-1} + o(1) as n \to \infty, since the gap is d - \max_{2 \leq i \leq n} |\lambda_i| \leq d - (2\sqrt{d-1} - o(1)). This asymptotic optimality criterion underpins the definition of Ramanujan graphs, which saturate the bound up to o(1) terms and represent the best possible expanders in terms of spectral properties.

Implications for optimal expanders

The Ramanujan bound, established by the Alon-Boppana theorem, provides a tight lower bound on the largest absolute value of the nontrivial eigenvalues \lambda_i (for i \geq 2) of the adjacency matrix of any d-regular graph, stating that \max_{i \geq 2} |\lambda_i| \geq 2\sqrt{d-1} - o(1) as the number of vertices grows. Graphs achieving \max_{i \geq 2} |\lambda_i| \leq 2\sqrt{d-1} are therefore optimal expanders, as they saturate this bound and deliver vertex and edge expansion properties that approach the theoretical limits observed in random d-regular graphs. This optimality implies that such graphs minimize the Cheeger constant up to constant factors, maximizing connectivity relative to their degree and size. Random d-regular graphs achieve this bound with high probability, meaning all nontrivial eigenvalues satisfy |\lambda_i| \leq 2\sqrt{d-1}, as proven by Huang, McKenzie, and Yau in 2024, resolving the Alon-Friedman conjecture and confirming that random constructions are Ramanujan graphs. This result builds on Friedman's theorem, which showed that for fixed d \geq 3 and sufficiently large n, a random d-regular graph on n vertices has \max_{i \geq 2} |\lambda_i| \leq 2\sqrt{d-1} + o(1) with probability $1 - o(1), providing a probabilistic benchmark for expander quality. However, explicit deterministic constructions of true Ramanujan graphs remain scarce and challenging, primarily relying on algebraic methods such as Cayley graphs over finite groups, with only a handful of infinite families known despite decades of research.^[15] In theoretical computer science, the Ramanujan bound's implications extend to efficient algorithms, where the small spectral gap d - \max_{i \geq 2} |\lambda_i| of optimal expanders yields upper bounds on mixing times of random walks, typically O\left(\frac{\log n}{1 - \max |\lambda_i|/d}\right), enabling fast uniform sampling and derandomization techniques in areas like approximate counting and error-correcting codes. Recent advances, such as the proof of edge universality for random regular graphs, further solidify the Ramanujan property by showing that the edge eigenvalue distribution converges to that of a deterministic model, confirming optimal spectral behavior for d \geq 3.^[16]

Definition of Ramanujan graphs

Formal spectral condition

A d-regular graph G on n vertices is a Ramanujan graph if it is connected and the absolute values of all non-trivial eigenvalues of its adjacency matrix A satisfy |\lambda_i| \leq 2\sqrt{d-1} for $2 \leq i \leq n, where the largest eigenvalue \lambda_1 = d$ is the trivial one with multiplicity 1. This spectral condition captures the graph's optimality as an expander, achieving the universal bound established by the Alon-Boppana theorem. Equivalently, the condition can be expressed using the normalized adjacency matrix \hat{A} = d^{-1} A, whose eigenvalues are \mu_i = \lambda_i / d. In this normalization, G is Ramanujan if |\mu_i| \leq \frac{2\sqrt{d-1}}{d} for all non-trivial eigenvalues i \geq 2, with \mu_1 = 1.^[17] The definition extends naturally to d-regular multigraphs, allowing multiple edges between vertices (so entries of A may exceed 1), while retaining the same eigenvalue bound on non-trivial \lambda_i. The name "Ramanujan graph" derives from Srinivasa Ramanujan's conjecture on the Ramanujan \tau-function, which bounds its coefficients by O(n^{11/2}) but was strengthened to |\tau(p)| \leq 2p^{11/2} using Deligne's proof; this analogy underpins the number-theoretic construction in the seminal work introducing the term. Ramanujan graphs differ from weakly Ramanujan graphs, which require only that the second-largest eigenvalue in absolute value satisfies the bound |\lambda_2| \leq 2\sqrt{d-1}, without constraining the smaller non-trivial eigenvalues.^[17]

Multigraphs versus simple graphs

Ramanujan graphs are typically defined in the context of multigraphs, which permit loops and multiple edges between vertices. The spectral condition for Ramanujanness—bounding the absolute values of nontrivial eigenvalues of the adjacency matrix by $2\sqrt{d-1} for a d-regular graph—applies directly to such structures, where the adjacency matrix entries count the number of edges (including loops as contributions of 2 to the diagonal). This allowance simplifies constructions, as algebraic methods like Cayley graphs on groups such as \mathrm{PGL}_2(\mathbb{F}_q) can naturally produce multiples without additional adjustments. For instance, the seminal Lubotzky–Phillips–Sarnak (LPS) construction yields explicit infinite families of d-regular Ramanujan multigraphs for d = p+1 where p is a prime congruent to 1 modulo 4. In contrast, simple Ramanujan graphs prohibit loops and multiple edges, adhering to the standard graph-theoretic definition of at most one edge per vertex pair. Achieving the Ramanujan bound under this restriction is more challenging, as many algebraic constructions initially generate multigraphs that must be modified. A classic example of a simple Ramanujan graph is the Petersen graph, which is 3-regular with non-trivial eigenvalues 1 and -2 (maximum absolute value 2 < 2√2 ≈ 2.828), confirming its optimality.^[18] For higher degrees, explicit simple examples are scarcer; however, the Marcus–Spielman–Srivastava theorem establishes the existence of infinite families of simple bipartite Ramanujan graphs for every degree d \geq 3.^[19] Probabilistic results, such as Friedman's theorem, confirm the existence of simple non-bipartite d-regular Ramanujan graphs for every fixed d ≥ 3, though constructing infinite explicit families remains an open problem as of 2025, particularly challenging for degrees like d=7 where algebraic methods do not directly apply.^[20]^[21] To bridge multigraphs and simple graphs, conversion techniques such as graph lifts and blow-ups preserve the Ramanujan property approximately. Lifts, which create coverings of a base graph by assigning voltages (group elements) to edges, can eliminate multiples while controlling eigenvalue growth to near the bound $2\sqrt{d-1}. Similarly, blow-up operations replace vertices with independent sets and redistribute edges, yielding simple graphs with spectral gaps asymptotically matching the original multigraph's. These methods, often applied iteratively, ensure that starting from a Ramanujan multigraph, one obtains arbitrarily large simple expanders close to optimal.^[22]

Constructions

Algebraic constructions via Cayley graphs

Algebraic constructions of Ramanujan graphs often leverage Cayley graphs, which provide a structured way to build regular graphs with desirable spectral properties using group theory. A Cayley graph \operatorname{Cay}(G, S) is defined for a finite group G and a symmetric subset S \subset G \setminus \{e\} of generators, where the vertex set is G and there is an edge between g and gs for each g \in G and s \in S. If |S| = d, the graph is d-regular and vertex-transitive, facilitating the computation of its adjacency eigenvalues through the irreducible representations of G: for a representation \chi, the corresponding eigenvalue is \frac{1}{\dim \chi} \sum_{s \in S} \chi(s), with multiplicity (\dim \chi)^2.^[23] Early explicit constructions of expander graphs via Cayley graphs, such as the Margulis construction from the 1970s, demonstrated the potential of this approach but fell short of the Ramanujan bound. In Margulis's construction, the graphs are Cayley graphs on the abelian group \mathbb{Z}_n \times \mathbb{Z}_n generated by eight elements derived from functions like S(a,b) = (a, a+b \mod n) and T(a,b) = (a+b \mod n, b), along with their inverses and shifts, yielding 8-regular graphs with at least 46 vertices that achieve a vertex expansion constant h(G_n) \geq 0.46 independent of n. These graphs form an infinite family of expanders with fixed degree and growing order, but their second-largest eigenvalue exceeds $2\sqrt{7}, approaching rather than attaining the optimal Ramanujan threshold.^[24] To achieve the Ramanujan bound, constructions employ non-abelian groups like \mathrm{SL}(2, q) or \mathrm{PGL}(2, \mathbb{F}_q), where representation theory provides tighter control over the spectrum. The irreducibility of representations ensures that non-trivial eigenvalues are bounded by analyzing the sums \sum_{s \in S} [\chi](/page/Chi)(s) for non-principal characters [\chi](/page/Chi), often yielding |\lambda| \leq 2\sqrt{d-1} when S is chosen appropriately from the group's structure. This leverages the group's algebraic properties to minimize the spectral gap deviation.^[23] These methods connect to number theory, particularly through Hecke operators and modular forms, which inform eigenvalue bounds in certain Cayley graphs on matrix groups over finite fields. For instance, the adjacency operator relates to Hecke correspondences on modular curves, allowing analytic techniques to confirm Ramanujan-level expansion by linking graph eigenvalues to coefficients of cusp forms.^[23] A broader algebraic framework for generating families of such graphs with fixed d and arbitrarily large order involves voltage graphs and their covers. A voltage graph assigns elements of a group to edges of a base graph, and the derived cover is a Cayley-like lift whose spectrum inherits controlled properties from the base, enabling iterative or lifted constructions that preserve or improve expansion while scaling the vertex count. This approach underpins families of Ramanujan graphs by ensuring the lifted eigenvalues remain within the optimal bound.^[23]

LPS Ramanujan graphs

The Lubotzky–Phillips–Sarnak (LPS) construction provides an explicit family of Ramanujan graphs using number-theoretic techniques from algebraic groups and modular forms. Introduced in 1988, it produces infinite families of d-regular Ramanujan graphs for certain degrees d \geq 3, where d = p + 1 and p is a prime congruent to 1 modulo 4.^[25] The graphs are defined as Cayley graphs \mathrm{Cay}(G, S) on the projective special linear group G = \mathrm{PSL}(2, \mathbb{F}_q), where q is a prime congruent to 1 modulo 4 and distinct from p. The generating set S consists of p+1 elements corresponding to the nonzero quadratic residues modulo p, embedded into G via a specific matrix representation that ensures S is symmetric and does not contain the identity. This construction yields a (p+1)-regular graph with |G| = \frac{q(q^2 - 1)}{2} vertices. The connection to quaternion algebras arises in the adelic formulation, where the graphs can be viewed as quotients of the Bruhat–Tits tree associated to the definite quaternion algebra over \mathbb{Q}(\sqrt{p}), ramified at p and infinity, facilitating the spectral analysis through strong approximation theorems.^[25] The proof that these graphs are Ramanujan relies on bounding the nontrivial eigenvalues of the adjacency operator. Using the Ihara zeta function to relate the spectrum to Hecke operators on modular forms, the eigenvalues are shown to satisfy |\lambda| \leq 2\sqrt{p} for the nontrivial ones, achieving the Alon–Boppana bound. This bound follows from Deligne's proof of the Ramanujan–Petersson conjecture, which implies that the Hecke eigenvalues (analogous to Ramanujan's tau function for the discriminant form) are at most $2\sqrt{n} in absolute value, directly applying to the representation-theoretic decomposition of the adjacency operator on the group.^[25] Infinite families exist for every such d \geq 3, obtained by fixing p and varying q over infinitely many suitable primes, yielding graphs of arbitrarily large order.^[25] Morgenstern extended the construction in 1994 to allow q to be any prime power congruent to 1 modulo 4, producing (p+1)-regular Ramanujan graphs for the same degrees while preserving the explicit nature and spectral optimality.^[26]

Random regular graph constructions

Random regular graphs are generated using the configuration model, which constructs a random d-regular multigraph on n vertices by pairing nd stubs (half-edges) randomly and allowing multiple edges and loops. This model approximates the uniform distribution over simple d-regular graphs when n is large and d is fixed, with the probability of multiple edges or loops vanishing as n \to \infty. Friedman's theorem establishes that, for fixed d \geq 3, a random d-regular graph on n vertices is Ramanujan with high probability as n \to \infty, meaning its second-largest eigenvalue \lambda_2 satisfies \lambda_2 \leq 2\sqrt{d-1} + o(1).^[27] This result proves Alon's conjecture that random regular graphs achieve the Ramanujan bound asymptotically almost surely.^[27] The original proof of Friedman's theorem employs the trace method, which bounds eigenvalues by analyzing traces of powers of the adjacency matrix and controlling the expected number of closed walks.^[27] Subsequent improvements, notably by Marcus, Spielman, and Srivastava, incorporate semi-definite programming techniques to refine the analysis and enable explicit constructions.^[28] To obtain explicit polynomial-time constructible Ramanujan graphs, random-like methods can be derandomized using expander graphs, such as through conditional expectations or zig-zag products that simulate the configuration model's behavior deterministically.^[29] This approach yields families of d-regular Ramanujan graphs for any fixed d \geq 3 and sufficiently large n, computable in time polynomial in \log n.^[29] Recent advances in 2024 confirm the Ramanujan property more precisely by proving edge universality: the second-largest and smallest eigenvalues of random d-regular graphs, for fixed d \geq 3, converge in distribution to the Tracy-Widom law after scaling, implying that such graphs are Ramanujan with probability approaching a positive constant (approximately 0.69) as n \to \infty.^[16]

Properties and optimality

Spectral gap achievement

Ramanujan graphs achieve the maximal possible spectral gap for d-regular graphs, precisely matching the lower bound on the second-largest eigenvalue provided by the Alon-Boppana theorem. For the adjacency matrix A of a d-regular graph on n vertices, the eigenvalues satisfy \lambda_1 = d > |\lambda_2| \geq \cdots \geq |\lambda_n|, and the spectral gap is \delta = d - \lambda_2. The Alon-Boppana theorem asserts that in any infinite family of d-regular graphs, \lambda_2 \geq 2\sqrt{d-1} - o(1) as n \to \infty, so \delta \leq d - 2\sqrt{d-1} + o(1). Ramanujan graphs realize this upper bound exactly, with \lambda_2 \leq 2\sqrt{d-1} (and symmetrically for the smallest eigenvalue).^[30] The trivial eigenvalues are d, associated with the all-ones eigenvector, and -d in the bipartite case, associated with the vector that is constant on each part of the bipartition but opposite in sign across parts. These account for the connected components and structural symmetry, leaving the remaining n-1 (or n-2 for bipartite) eigenvalues as non-trivial.^[10] For non-trivial eigenvalues in algebraic constructions, such as Cayley graphs over finite groups like \mathrm{PGL}_2(\mathbb{F}_q), the bound |\lambda_i| \leq 2\sqrt{d-1} follows from explicit computations using the representation theory of the group, which classifies all irreducible representations and ensures no eigenvalue exceeds the Ramanujan threshold. This representation-theoretic approach guarantees the absence of outlier eigenvalues larger than the Alon-Boppana limit. The resulting spectral gap \delta = d - 2\sqrt{d-1} yields optimal mixing times for the simple random walk on Ramanujan graphs, bounded by O(\log n / \delta) = O(\log n / (d - 2\sqrt{d-1})), which is asymptotically tight for d-regular expanders and superior to suboptimal expanders with smaller gaps.^[10] In random constructions of near-Ramanujan graphs, such as models of random d-regular graphs, the distribution of non-trivial eigenvalues shows that almost all lie close to the boundary $2\sqrt{d-1}, with only a vanishing fraction deviating significantly, underscoring the spectral optimality and universality in these ensembles.^[31]

Edge expansion guarantees

Ramanujan graphs provide strong guarantees on edge expansion, a key combinatorial measure of how well the graph connects subsets of vertices to the rest of the graph. The edge expansion, denoted \phi(G), is defined as \phi(G) = \min_{S \subseteq V, |S| \leq n/2} \frac{|E(S, V \setminus S)|}{|S|}, where n = |V|. For a d-regular Ramanujan graph G, the spectral condition \lambda_2 \leq 2\sqrt{d-1} (with \lambda_2 the second-largest eigenvalue of the adjacency matrix) implies \phi(G) \geq \frac{d - 2\sqrt{d-1}}{2}. This bound follows from the general inequality for d-regular graphs, \phi(G) \geq \frac{d - \lambda_2}{2}, which certifies expansion via the spectral gap.^[10] More generally, vertex isoperimetry bounds ensure robust connectivity for arbitrary subsets. By the expander mixing lemma, for any S \subseteq V, the number of edges leaving S satisfies

|E(S, V \setminus S)| \geq \frac{d |S| (n - |S|)}{n} - 2\sqrt{d-1} \cdot \sqrt{|S| (n - |S|)}.

This provides an explicit lower bound incorporating the spectral gap, with the second term representing the deviation controlled by the nontrivial eigenvalues. For small sets (|S| \ll n), this simplifies to nearly d |S|, while for balanced sets, the guarantee remains \Omega(d |S| (1 - |S|/n)) up to the gap factor. Such properties make Ramanujan graphs optimal for applications requiring uniform mixing and connectivity.^[10] In the bipartite setting, Ramanujan graphs yield balanced expanders with comparable guarantees. Explicit constructions, such as the Margulis graphs, produce d-regular bipartite graphs on $2n vertices with the same spectral bound \lambda_2 \leq 2\sqrt{d-1}, ensuring symmetric expansion from both parts. These achieve vertex expansion close to d/2 for small sets on either side, with constants derived analogously from the spectral gap, making them ideal for balanced partitioning tasks.^[10] These expansion properties enable practical uses, such as in sorting networks, where Ramanujan graphs facilitate explicit constructions of depth O(\log n) sorters with polynomial size, leveraging their near-optimal mixing to route elements efficiently across layers. However, while spectrally optimal, explicit Ramanujan constructions like LPS and Margulis graphs are restricted to degrees d where d-1 is a prime power, and generating them incurs computational overhead from algebraic computations over finite fields.^[10]

Applications

In computer science algorithms

Ramanujan graphs have enabled significant advances in algorithmic efficiency through their optimal spectral properties, particularly in constructing explicit expanders that support derandomization and parallel computation. A landmark result is the explicit construction theorem by Marcus, Spielman, and Srivastava, which provides a deterministic polynomial-time algorithm to generate bipartite d-regular Ramanujan graphs for every degree d \geq 3 and any sufficiently large even number of vertices.^[32] This breakthrough resolved a long-standing open problem by yielding families of graphs with nearly optimal spectral gaps, constructible in time polynomial in the number of vertices. In derandomization, Ramanujan graphs facilitate the replacement of truly random walks with pseudorandom generators derived from walks on these graphs, which exhibit mixing times close to those of random graphs while being fully deterministic. This approach derandomizes algorithms relying on expander properties, such as approximating matrix multiplication, by ensuring that short walks suffice to produce statistically close distributions to uniform randomness. Expander random walks provide derandomized approximations in linear algebra tasks. Ramanujan graphs, as optimal expanders, enhance load balancing and hashing schemes, including cuckoo hashing, where superior expansion guarantees optimal space usage while preserving constant-time operations. In random-walk cuckoo hashing, the use of expander graphs minimizes insertion conflicts by ensuring rapid mixing, allowing hash tables to operate with load factors approaching 1 without performance degradation.^[33] This optimality stems from bounded second eigenvalues, which bound the probability of collisions far better than suboptimal expanders, enabling practical implementations with O(1) worst-case lookup and near-linear space. Parallel algorithms benefit from Ramanujan graphs through expander walks that accelerate solvers for linear systems and matrix operations. Spielman and Teng developed nearly linear-time preconditioners for symmetric diagonally dominant systems using spectral sparsification and walks on expanders, which parallelize effectively across processors due to the graphs' low-diameter connectivity. These techniques extend to parallel matrix multiplication, where Ramanujan-based walks approximate products with high accuracy in logarithmic rounds.

In cryptography and coding theory

Ramanujan graphs have found significant applications in cryptography due to their optimal expander properties, which enable the construction of pseudorandom functions and secure protocols. The Lubotzky–Phillips–Sarnak (LPS) Ramanujan graphs, constructed as Cayley graphs over finite fields, have been employed to build cryptographic hash functions by modeling them as random walks on the graph, where the input message determines the walk length and starting vertex, and the output is the ending vertex. These hash functions exhibit strong pseudorandomness because the spectral gap of LPS graphs ensures that short walks mix rapidly, approximating a uniform distribution over the vertices, which is crucial for collision resistance and preimage security. Such hash functions based on LPS graphs have been analyzed for use in broader cryptographic primitives, including commitment schemes, where the binding and hiding properties leverage the graph's expansion to prevent efficient forgery or revelation of committed values. In post-quantum cryptography, Ramanujan graphs underpin secure protocols resistant to quantum attacks, particularly through supersingular isogeny graphs, which are a family of Ramanujan expanders. These graphs, with vertices representing supersingular elliptic curves and edges corresponding to isogenies of a fixed degree, provided the foundation for schemes like the Supersingular Isogeny Diffie-Hellman (SIDH) key exchange, where key generation involved sampling paths on the graph. Although SIDH was broken in 2022,^[34] the Ramanujan property guarantees excellent expansion, allowing short paths to behave pseudorandomly. Supersingular isogeny graphs remain of interest for other post-quantum protocols under active research. Work by Feigon and collaborators has analyzed the number-theoretic security of these graphs from a pre-2022 perspective, supporting their study in post-quantum settings.^[35] Security proofs for Ramanujan graph-based cryptosystems often hinge on the spectral uniqueness of these graphs, which makes them computationally indistinguishable from random regular graphs under certain assumptions. The bounded nontrivial eigenvalues (at most $2\sqrt{d-1} for degree d) ensure that the adjacency matrix's spectrum closely mimics that of a random graph, complicating efforts to exploit structural biases for attacks like distinguishing or cycle detection. This pseudorandomness supports provable security reductions, such as reducing collision-finding in hash functions to hard graph problems.^[35] In coding theory, Ramanujan graphs serve as building blocks for high-performance error-correcting codes, particularly low-density parity-check (LDPC) codes and expander codes, owing to their superior expansion that minimizes decoding errors. The zig-zag product, when applied iteratively starting from small Ramanujan graphs, constructs large families of explicit expanders that preserve near-optimal spectral gaps, enabling the design of LDPC codes with constant degree and girth properties that guarantee efficient iterative decoding. These codes achieve low error rates under belief propagation decoding, performing comparably to or better than random LDPC codes in simulations, with expansion ensuring that small sets of erroneous bits do not propagate during correction. Pizer's construction of Ramanujan graphs, based on supersingular elliptic curves and isogenies, has been particularly useful for expander codes, where the bipartite graph's left vertices represent code bits and right vertices parity checks. Using a d-regular Ramanujan expander, these codes attain a rate of $1 - O(1/\sqrt{d}), approaching the Shannon limit for large d, while the optimal expansion bounds the relative distance and enables correction of a constant fraction of errors with linear-time algorithms. The spectral properties guarantee that unique decoding succeeds for errors up to a fraction proportional to the expansion parameter, providing robust performance in noisy channels.^[36]

References

[1]
[PDF] What Is... a Ramanujan Graph? | OSU Math
Jul 26, 2022 · d-regular bipartite Ramanujan graph with n vertices. However, the bipartiteness means these graphs are Ramanujan in a weaker sense—they are not.
[2]
https://arxiv.org/abs/1909.06988
[3]
[math/0406208] Ramanujan Complexes of Type $\tilde{A_d}$ - arXiv
Jun 10, 2004 · We define and construct Ramanujan complexes. These are simplicial complexes which are higher dimensional analogues of Ramanujan graphs. They are ...
[4]
[PDF] Spectral graph theory
For a d-regular graph, λ1 = d, and the corresponding eigenvector is the all 1 vector. If the graph is disconnected, then its adjacency matrix decomposes into ...
[5]
[PDF] CS 252, Lecture 6: Spectral Graph Theory
In this lecture, we give an overview of spectral graph theory, where in we use tools from Linear Algebra to study graphs. We demonstrate how we can “read ...
[6]
[PDF] The Adjacency Matrix and The nth Eigenvalue 3.1 About these notes ...
Sep 5, 2012 · So, we see that the largest adjacency eigenvalue of a d-regular graph is d, and its corresponding eigenvector is the constant vector. We could ...
[7]
[PDF] Lecture 7 1 Normalized Adjacency and Laplacian Matrices
Sep 13, 2016 · In this lecture, we introduce normalized adjacency and Laplacian matrices. We state and begin to prove Cheeger's inequality, which relates ...
[8]
[PDF] Lecture Notes on Graph Partitioning, Expanders and Spectral Methods
will study spectral graph algorithms, that is, graph algorithms that make use of eigenvalues and eigenvectors of the normalized Laplacian of the given graph.
[9]
[PDF] Eigenvalues and the Laplacian of a graph - Fan Chung Graham
Basically, the eigenvalues are defined here in a general and “normalized” form. Although this might look a little complicated at first, our eigenvalues relate ...Missing: expansion | Show results with:expansion
[10]
[PDF] Expander graphs and their applications - CS - Huji
Aug 7, 2006 · Expander graphs are highly connected graphs, where disconnecting a large part requires severing many edges. They are also defined by rapid ...
[11]
[PDF] Expander Graphs - Harvard SEAS
Page 9. 88 Expander Graphs. it is known that Ramanujan graphs actually have vertex expansion. D/2 − O(1) for sets of density O(1), which is tight in the sense ...
[12]
[PDF] Combinatorial vs spectral expansion (Cheeger's Inequality) - CS 6810
In this note, we will look at the connection between the eigenvalue gap and a combina- torial graph parameter, called “expansion”". Let G be a d-regular graph ...
[13]
Approximate Moore Graphs are good expanders - ScienceDirect.com
In general, low diameter does not guarantee good expansion. Consider, e.g., a graph on n vertices that is a disjoint union of two cliques, each of size ...Missing: poor | Show results with:poor
[14]
https://doi.org/10.1007/BF02579166
[15]
[PDF] Explicit near-Ramanujan graphs of every degree
Sep 15, 2019 · Of course, to get a construction which is overall explicit, we need to derandomize the Fried- man/Bordenave analysis for this base graph H. The ...
[16]
Ramanujan Property and Edge Universality of Random Regular ...
Abstract page for arXiv paper 2412.20263: Ramanujan Property and Edge Universality of Random Regular Graphs.
[17]
[PDF] A generalized Alon-Boppana bound and weak Ramanujan graphs
Feb 10, 2016 · We examine the vertex expansion and edge expansion of weak Ramanujan graphs and then use the expansion properties among other methods to derive ...
[18]
[PDF] Ramanujan Graphs - Department of Mathematics and Statistics
In particular, Theorem 5 implies the Alon-Boppana theorem sinceλ(X) ≥ λ1(X). 2. Cayley graphs. There is a simple procedure for constructing k-regular graphs ...<|control11|><|separator|>
[19]
[PDF] Interlacing families I: Bipartite Ramanujan graphs of all degrees
We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of.
[20]
[PDF] Ramanujan Coverings of Graphs - Institute for Advanced Study
Jul 13, 2016 · Marcus, Spielman and Srivastava have already shown that every graph has a one-sided Ra- manujan 2-covering [MSS15a]. Thus, if a family of ...
[21]
[PDF] Ramanujan Graphs: An Introduction
The first explicit constructions of Ramanujan graphs were given (independently) by Margulis [42] and Lubotzky, Phillips and Sarnak [40] in 1988, almost twenty.
[22]
https://www.ias.edu/sites/default/files/math/csdm/15-16/HallPuSa2016.pdf
[23]
https://mast.queensu.ca/~murty/RamanujanGraphs-IJDM.pdf
[24]
A proof of Alon's second eigenvalue conjecture and related problems
May 5, 2004 · In this paper we show the following conjecture of Noga Alon. Fix a positive integer d>2 and real epsilon > 0; consider the probability that a random d-regular ...Missing: original | Show results with:original
[25]
Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
Apr 15, 2013 · Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees. Authors:Adam Marcus, Daniel A. Spielman, Nikhil Srivastava.
[26]
[1604.03544] Ramanujan Graphs in Polynomial Time - arXiv
Apr 12, 2016 · Here, we provide a polynomial time algorithm to compute certain expected characteristic polynomials related to this construction.
[27]
[PDF] eigenvalues and expanders n. alon - TAU
In Section 3 we observe that. Page 3. EIGENVALUES AND EXPANDERS. 85 this relationship implies a similar one between eigenvalues and expanders. In Section. 4 we ...
[28]
[PDF] The Distribution of the Largest Non-trivial Eigenvalues in Families of ...
In Figure 7 we plot the percentage of graphs in each sample of 1000 from the four families that are Ramanujan (the first plot is the percentage against the ...
[29]
Interlacing families I: Bipartite Ramanujan graphs of all degrees
Marcus, Daniel A. Spielman, Nikhil Srivastava. Abstract. We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree ...
[30]
An Analysis of Random-Walk Cuckoo Hashing - SIAM.org
Cuckoo hashing provides a useful methodology for building practical, high-performance hash tables. The essential idea of cuckoo hashing is to combine the power ...
[31]
[1806.05709] Ramanujan graphs in cryptography - arXiv
Jun 14, 2018 · In this paper we study the security of a proposal for Post-Quantum Cryptography from both a number theoretic and cryptographic perspective.
[32]
[PDF] Expander Codes - Information Theory, IEEE Transactions on
As these codes are derived from expander graphs, we call them "expander codes." Expander codes belong to the class of low-density parity-check codes introduced ...