Ramanujan Graphs

Imagine you want to build a communication network: every node connects to exactly $d$ others (a $d$-regular graph), you want as few wires as possible, yet a message must spread quickly from any node to any other. How well-connected can you make it?

The answer is encoded in the eigenvalues of the graph's adjacency matrix. For a $d$-regular graph on $n$ vertices the largest eigenvalue is always $d$. The second-largest eigenvalue $\lambda_2$ controls how fast information (or a random walk) propagates: the spectral gap $d - \lambda_2$ must be large for rapid mixing.

In 1988 the Alon-Boppana theorem proved that no infinite family of $d$-regular graphs can keep $\lambda_2$ below $2\sqrt{d-1}$. That lower bound is a wall — you simply cannot do better. A $d$-regular graph is called a Ramanujan graph when it actually hits that wall:

$$\lambda_2 \;\le\; 2\sqrt{d-1}$$

The name honours the mathematician Srinivasa Ramanujan: the first explicit constructions, by Lubotzky-Phillips-Sarnak and Margulis (both 1988), relied on deep results about Ramanujan's tau function and the Ramanujan conjecture (proved by Deligne in 1974). Hitting the Alon-Boppana bound with a concrete, efficiently describable graph turned out to require some of the deepest machinery in twentieth-century number theory.

The demo below lets you compare two 3-regular graphs side by side. The Ramanujan graph (left) is the Petersen graph: $\lambda_2 = \sqrt{5} \approx 2.24$, far below the Alon-Boppana bound $2\sqrt{2} \approx 2.83$, giving a large spectral gap of $\approx 0.76$. The ordinary graph (right) is a 3-regular graph whose $\lambda_2 \approx 2.66$, producing a much smaller gap of $\approx 0.34$.

<!-- {{c_layout_comment}} -->
<div class="demo-wrap">
  <div class="panel" id="panel-ram">
    <h3 class="panel-title ram">{{label_ramanujan}}</h3>
    <div class="eigen-row">
      <span class="eigen-label">{{label_lambda2}}</span>
      <span class="eigen-val" id="lam-ram">2.236</span>
      <span class="eigen-label">{{label_gap}}</span>
      <span class="eigen-val gap" id="gap-ram">0.764</span>
    </div>
    <canvas id="cv-ram" width="210" height="210"></canvas>
    <div class="mix-bar-wrap" title="{{title_mix}}">
      <div class="mix-bar" id="mix-ram"></div>
    </div>
    <div class="step-info" id="steps-ram">{{label_steps}} 0</div>
  </div>
  <div class="panel" id="panel-ord">
    <h3 class="panel-title ord">{{label_ordinary}}</h3>
    <div class="eigen-row">
      <span class="eigen-label">{{label_lambda2}}</span>
      <span class="eigen-val" id="lam-ord">2.655</span>
      <span class="eigen-label">{{label_gap}}</span>
      <span class="eigen-val gap bad" id="gap-ord">0.345</span>
    </div>
    <canvas id="cv-ord" width="210" height="210"></canvas>
    <div class="mix-bar-wrap" title="{{title_mix}}">
      <div class="mix-bar" id="mix-ord"></div>
    </div>
    <div class="step-info" id="steps-ord">{{label_steps}} 0</div>
  </div>
</div>
<div class="hint-row">{{hint_para}}</div>
<div class="btns">
  <button id="btn-step">{{btn_step}}</button>
  <button id="btn-run">{{btn_run}}</button>
  <button id="btn-reset" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_root}} */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: transparent; }
.demo-wrap { display: flex; gap: 12px; justify-content: center; flex-wrap: wrap; margin-bottom: 8px; }
.panel { display: flex; flex-direction: column; align-items: center; gap: 6px; min-width: 200px; }
.panel-title { font-size: .95rem; font-weight: 700; padding: 2px 10px; border-radius: 6px; }
.panel-title.ram { background: #d4edda; color: #155724; }
.panel-title.ord { background: #fde8d8; color: #7a3000; }
.eigen-row { display: flex; align-items: center; gap: 4px; font-size: .78rem; }
.eigen-label { color: #555; }
.eigen-val { font-weight: 700; color: #1d3557; }
.eigen-val.gap { color: #0a7d33; }
.eigen-val.gap.bad { color: #c92f3c; }
canvas { border-radius: 10px; background: #f4f7fa; border: 1px solid #d0d8e4; }
.mix-bar-wrap { width: 210px; height: 14px; background: #e0e6ed; border-radius: 7px; overflow: hidden; position: relative; }
.mix-bar { height: 100%; width: 0%; background: #0a7d33; border-radius: 7px; transition: width .3s; }
#mix-ord .mix-bar, .panel#panel-ord .mix-bar { background: #c92f3c; }
.step-info { font-size: .78rem; color: #555; }
.hint-row { font-size: .82rem; color: #444; line-height: 1.45; margin: 6px 0 4px; max-width: 440px; text-align: center; margin-left: auto; margin-right: auto; }
.btns { display: flex; gap: .5rem; justify-content: center; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Press Step to advance the random walk one hop, or Run to animate. Notice how the walk on the Ramanujan graph spreads out faster and mixes more uniformly — the large spectral gap forces rapid convergence to the uniform distribution. The ordinary graph's walker stays clumped for much longer.

The Ramanujan graph story is solved — but the journey to that solution crossed some of the deepest areas of mathematics.

• The Alon-Boppana bound (1986, strengthened by Nilli 1991): for any infinite family of $d$-regular graphs, $\limsup \lambda_2 \ge 2\sqrt{d-1}$. This sets the wall that Ramanujan graphs touch.
• Lubotzky-Phillips-Sarnak (LPS, 1988): constructed explicit $d$-regular Ramanujan graphs for $d = p+1$ where $p$ is prime, using Cayley graphs of $\mathrm{PGL}_2(\mathbb{F}_q)$ and the Ramanujan conjecture (Deligne's theorem) to control eigenvalues.
• Margulis (1988): independent construction using different algebraic groups; also degree $p+1$ for prime $p$.
• The big open question remained: do Ramanujan graphs exist for all degrees $d \ge 3$ and all sizes $n$? Not just primes?
• Marcus-Spielman-Srivastava (MSS, 2015) proved existence for all $d$-regular bipartite graphs using the method of interlacing polynomials — a probabilistic, non-constructive argument. The paper resolved a 2004 conjecture of Weaver (equivalent to the Kadison-Singer problem), which itself had roots in quantum mechanics and operator theory.

So the status is: existence is settled for all degrees (MSS 2015); explicit efficient constructions for every degree remain an active research frontier. For prime degrees the LPS graphs are concrete, polynomial-time computable, and used in practice. The field connects number theory, representation theory, combinatorics, and functional analysis.

A graph that is simultaneously sparse and maximally well-connected is a powerful object across computer science and mathematics:

• Error-correcting codes: expander graphs give simple, linear-time-encodable/decodable codes with constant rate and constant relative distance — a key ingredient in modern coding theory.
• Pseudorandomness: expander walks produce near-uniform samples using far fewer random bits than naive methods, which matters for derandomization and complexity lower bounds. See the connection to in-context learning when the walk generates training data.
• Network design: communication and routing networks need high bisection bandwidth with few links; Ramanujan graphs are the theoretical ideal.
• Cryptographic hash functions: some hash functions (e.g., the Charles-Goren-Lauter hash) are built on Ramanujan graphs; a collision would require finding a short cycle — believed hard.
• Metric embeddings and geometry of Banach spaces: expanders cannot be embedded with low distortion into $\ell_1$ or Hilbert spaces — useful in hardness-of-approximation proofs.
• Quantum computing: expander-based constructions appear in quantum error-correcting codes and the analysis of quantum simulation algorithms.

Wherever you need information to spread fast, random walks to mix quickly, or codes to be resilient, the spectral gap is the lever — and Ramanujan graphs are as good as that lever can get.

Ramanujan graphs answer a beautifully precise question: how well-connected can a $d$-regular graph be? The Alon-Boppana theorem says no infinite family can push $\lambda_2$ below $2\sqrt{d-1}$; Ramanujan graphs are exactly those that reach it. Constructing them took Deligne's proof of the Ramanujan conjecture in 1974, the LPS and Margulis constructions in 1988, and the MSS resolution of the Kadison-Singer problem in 2015.

The spectral gap is not an abstract curiosity. It controls mixing times of random walks, the quality of error-correcting codes, the security of cryptographic hash functions, and the efficiency of network routing. Whenever you need a sparse structure that behaves as if it were dense, you are secretly wishing for a Ramanujan graph — and now you know exactly how good "best possible" can be.