Introduction

Imagine you want to build a communication network: every node connects to exactly dd others (a dd-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 dd-regular graph on nn vertices the largest eigenvalue is always dd. The second-largest eigenvalue λ2\lambda_2 controls how fast information (or a random walk) propagates: the spectral gap d−λ2d - \lambda_2 must be large for rapid mixing.

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

λ2  ≤  2d−1\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.

Try It: Spectral Gap vs. Mixing

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

<!-- Two-panel layout: Ramanujan graph (left) vs ordinary graph (right) -->
<div class="demo-wrap">
  <div class="panel" id="panel-ram">
    <h3 class="panel-title ram">Ramanujan Graph</h3>
    <div class="eigen-row">
      <span class="eigen-label">λ₂ =</span>
      <span class="eigen-val" id="lam-ram">2.236</span>
      <span class="eigen-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="Mixing score: how close visit counts are to uniform (higher is better)">
      <div class="mix-bar" id="mix-ram"></div>
    </div>
    <div class="step-info" id="steps-ram">Steps: 0</div>
  </div>
  <div class="panel" id="panel-ord">
    <h3 class="panel-title ord">Ordinary Graph</h3>
    <div class="eigen-row">
      <span class="eigen-label">λ₂ =</span>
      <span class="eigen-val" id="lam-ord">2.655</span>
      <span class="eigen-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="Mixing score: how close visit counts are to uniform (higher is better)">
      <div class="mix-bar" id="mix-ord"></div>
    </div>
    <div class="step-info" id="steps-ord">Steps: 0</div>
  </div>
</div>
<div class="hint-row">The red dot is a random walker. The <b>mixing bar</b> measures how uniformly the walker has visited all nodes. A large spectral gap (Ramanujan) means faster, more uniform mixing.</div>
<div class="btns">
  <button id="btn-step">Step</button>
  <button id="btn-run">Run</button>
  <button id="btn-reset" class="ghost">Reset</button>
</div>

/* Base styles for the two-panel spectral gap demo. */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Spectral gap demo: compare a Ramanujan graph vs an ordinary 3-regular graph.
// Both have degree 3. Ramanujan = Petersen (10 nodes); Ordinary = random 3-regular (12 nodes).

// Ramanujan graph: the Petersen graph (3-regular, 10 nodes).
// λ_2 = sqrt(5) ≈ 2.236, Alon-Boppana bound = 2*sqrt(2) ≈ 2.828.
const GRAPH_RAM = {
  n: 10,
  adj: [
    [1,4,5],[0,2,6],[1,3,7],[2,4,8],[3,0,9],
    [0,7,8],[1,8,9],[2,5,9],[3,5,6],[4,6,7]
  ]
};

// Ordinary graph: a random 3-regular graph with larger lambda2 (less optimal).
// 12-node 3-regular graph: λ_2 ≈ 2.655, gap ≈ 0.345 (half of Petersen's 0.764).
const GRAPH_ORD = {
  n: 12,
  adj: [
    [1,3,5],[4,0,8],[11,6,3],[0,5,2],[1,7,9],
    [3,0,6],[11,2,5],[4,10,9],[10,11,1],[10,4,7],
    [9,7,8],[2,6,8]
  ]
};

// Position nodes in a circle for clean rendering.
function circleLayout(n, cx, cy, r) {
  return Array.from({length: n}, (_, i) => ({
    x: cx + r * Math.cos(2 * Math.PI * i / n - Math.PI / 2),
    y: cy + r * Math.sin(2 * Math.PI * i / n - Math.PI / 2)
  }));
}

// Random walk state: current node and visit counts for each graph.
let walkers = { ram: 0, ord: 0 };
let visitCounts = {
  ram: new Array(GRAPH_RAM.n).fill(0),
  ord: new Array(GRAPH_ORD.n).fill(0)
};
let totalSteps = { ram: 0, ord: 0 };
let running = false;
let rafId = null;

// Precomputed eigenvalues for display. The Petersen graph is a known Ramanujan graph.
// Petersen graph: lambda_2 = sqrt(5) ≈ 2.236 < 2*sqrt(2) ≈ 2.828 (Ramanujan).
// Ordinary graph: lambda_2 ≈ 2.655 < 2.828 but MUCH larger gap than Petersen (0.345 vs 0.764).
const LAMBDA2 = { ram: 2.236, ord: 2.655 };
const DEG = 3;
const ALON_BOPPANA = 2 * Math.sqrt(DEG - 1);
const GAP = {
  ram: +(DEG - LAMBDA2.ram).toFixed(3),
  ord: +(DEG - LAMBDA2.ord).toFixed(3)
};

// Draw graph on canvas: edges, then nodes colored by visit heat.
function draw(gKey, canvas, graph, pos) {
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);
  const walker = walkers[gKey];
  const counts = visitCounts[gKey];
  const maxCount = Math.max(1, ...counts);

  // Draw edges in light color.
  ctx.strokeStyle = '#c8d4e0';
  ctx.lineWidth = 1.2;
  for (let u = 0; u < graph.n; u++) {
    for (const v of graph.adj[u]) {
      if (v > u) {
        ctx.beginPath();
        ctx.moveTo(pos[u].x, pos[u].y);
        ctx.lineTo(pos[v].x, pos[v].y);
        ctx.stroke();
      }
    }
  }

  // Draw nodes: heat map by visit count, walker highlighted in red.
  for (let u = 0; u < graph.n; u++) {
    const heat = counts[u] / maxCount;
    const r = 9 + heat * 5;
    ctx.beginPath();
    ctx.arc(pos[u].x, pos[u].y, r, 0, 2 * Math.PI);
    const g = Math.round(125 + (1 - heat) * 130);
    const b = Math.round(80 + (1 - heat) * 174);
    ctx.fillStyle = u === walker ? '#e63946' : `rgb(29,${g},${b})`;
    ctx.fill();
    ctx.strokeStyle = u === walker ? '#9b1a23' : '#fff';
    ctx.lineWidth = u === walker ? 2.5 : 1.2;
    ctx.stroke();
    // Node label.
    ctx.fillStyle = '#fff';
    ctx.font = 'bold 10px system-ui';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(u, pos[u].x, pos[u].y);
  }
}

// Total variation distance to uniform, mapped to a 0-1 mixing score.
function mixScore(counts, n) {
  const total = counts.reduce((a, b) => a + b, 0);
  if (total === 0) return 0;
  const expected = total / n;
  let tv = 0;
  for (const c of counts) tv += Math.abs(c - expected);
  const tvDist = tv / (2 * total); // Total variation distance = sum|p_i - 1/n| / 2, clamped to [0,1].
  return Math.max(0, 1 - tvDist * 2);
}

const cvRam = document.getElementById('cv-ram');
const cvOrd = document.getElementById('cv-ord');
const posRam = circleLayout(GRAPH_RAM.n, 105, 105, 82);
const posOrd = circleLayout(GRAPH_ORD.n, 105, 105, 82);

function updateUI() {
  draw('ram', cvRam, GRAPH_RAM, posRam);
  draw('ord', cvOrd, GRAPH_ORD, posOrd);

  const scoreRam = mixScore(visitCounts.ram, GRAPH_RAM.n);
  const scoreOrd = mixScore(visitCounts.ord, GRAPH_ORD.n);

  document.getElementById('mix-ram').style.width = (scoreRam * 100).toFixed(1) + '%';
  document.getElementById('mix-ord').style.width = (scoreOrd * 100).toFixed(1) + '%';

  document.getElementById('steps-ram').textContent = fmt('Steps: %ram%', { ram: totalSteps.ram });
  document.getElementById('steps-ord').textContent = fmt('Steps: %ord%', { ord: totalSteps.ord });
}

function step() {
  for (const gKey of ['ram', 'ord']) {
    const graph = gKey === 'ram' ? GRAPH_RAM : GRAPH_ORD;
    const nbrs = graph.adj[walkers[gKey]];
    walkers[gKey] = nbrs[Math.floor(Math.random() * nbrs.length)];
    visitCounts[gKey][walkers[gKey]]++;
    totalSteps[gKey]++;
  }
  updateUI();
}

function resetAll() {
  walkers = { ram: 0, ord: 0 };
  visitCounts = {
    ram: new Array(GRAPH_RAM.n).fill(0),
    ord: new Array(GRAPH_ORD.n).fill(0)
  };

  totalSteps = { ram: 0, ord: 0 };
  visitCounts.ram[0] = 1;
  visitCounts.ord[0] = 1;
  stopRun();
  updateUI();
}

function stopRun() {
  running = false;
  if (rafId) { cancelAnimationFrame(rafId); rafId = null; }
  document.getElementById('btn-run').textContent = 'Run';
}

function runLoop() {
  if (!running) return;
  for (let i = 0; i < 3; i++) step();
  rafId = requestAnimationFrame(runLoop);
}

document.getElementById('btn-step').addEventListener('click', () => { stopRun(); step(); });
document.getElementById('btn-run').addEventListener('click', () => {
  running = !running;
  document.getElementById('btn-run').textContent = running ? 'Stop' : 'Run';
  if (running) runLoop();
});
document.getElementById('btn-reset').addEventListener('click', resetAll);

// Show precomputed eigenvalues in the UI on load.
document.getElementById('lam-ram').textContent = LAMBDA2.ram.toFixed(3);
document.getElementById('lam-ord').textContent = LAMBDA2.ord.toFixed(3);
document.getElementById('gap-ram').textContent = GAP.ram.toFixed(3);
document.getElementById('gap-ord').textContent = GAP.ord.toFixed(3);

resetAll();
Result
Console

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 Real Complexity

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 dd-regular graphs, lim sup⁡λ2≥2d−1\limsup \lambda_2 \ge 2\sqrt{d-1}. This sets the wall that Ramanujan graphs touch.
  • Lubotzky-Phillips-Sarnak (LPS, 1988): constructed explicit dd-regular Ramanujan graphs for d=p+1d = p+1 where pp is prime, using Cayley graphs of PGL2(Fq)\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+1p+1 for prime pp.
  • The big open question remained: do Ramanujan graphs exist for all degrees d≥3d \ge 3 and all sizes nn? Not just primes?
  • Marcus-Spielman-Srivastava (MSS, 2015) proved existence for all dd-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.

Where It Matters

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 ℓ1\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.

Conclusion

Ramanujan graphs answer a beautifully precise question: how well-connected can a dd-regular graph be? The Alon-Boppana theorem says no infinite family can push λ2\lambda_2 below 2d−12\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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/ramanujan-graphs/Content licensed under CC BY-NC 4.0.