What the Ramanujan graphs are actually for

A network is only as good as its bottlenecks. The Ramanujan graphs are sparse networks with provably no bottlenecks at all — as well connected as a graph of their degree can ever be — and the proof that they exist runs through one of the deepest theorems in number theory.

The objects in question are #expander-graphs: networks that are simultaneously sparse — each node touches only d others, for some fixed small d — and so thoroughly connected that every subset of nodes, however adversarially chosen, has a large fraction of its edges leading out. A random walk on an expander forgets its starting point almost immediately. Sparse graphs that behave, for every purpose that matters, like dense random ones: that is the engineering dream, and expanders deliver it.

Quality is measured by a spectrum. List the eigenvalues of the graph's adjacency matrix. The largest is exactly d, always, and carries no information; everything lives in the rest. Write λ for the largest nontrivial eigenvalue in absolute value: the distance between d and λ — the #spectral-gap — controls how fast walks mix and how badly any cut can bottleneck the graph. Smaller λ, better network. So the obvious question is how small λ can be made.

There is a floor. Alon and Boppana proved that for d-regular graphs with many vertices, λ cannot fall meaningfully below 2√(d−1).¹ A graph that achieves λ ≤ 2√(d−1) is therefore spectrally optimal — as expanding as its degree permits. These are the graphs that Lubotzky, Phillips and @Sarnak named Ramanujan graphs in 1988.

The name is the honest part. The Lubotzky–Phillips–Sarnak construction builds the graphs out of quaternion arithmetic, and verifying the eigenvalue bound turns exactly on the Ramanujan–Petersson conjecture — a 1916 conjecture of @Ramanujan about the coefficients of a modular form, proved by Deligne in 1974 as a consequence of the Weil conjectures.² The best possible networks exist because a century-old statement about a q-series turned out to be true.

What optimal connectivity buys

The first application is stretching randomness. To shrink the error of a randomized algorithm, the naive method repeats it with fresh random bits each time. Run the repetitions instead at the successive steps of a random walk on an expander and the error still decays almost as fast — while the walk consumes only a handful of additional random bits per step. Whole derandomization results stand on this trick, including Reingold's theorem that undirected maze navigation needs no randomness at all.

The second is coding. Sipser and Spielman showed that a bipartite expander used as a parity-check structure yields #error-correcting-codes that can be decoded in linear time by purely local repairs — a design whose descendants, the LDPC codes, now sit in Wi-Fi and 5G standards. The property doing the work is exactly the absence of bottlenecks: errors cannot hide in a badly connected corner, because there are none.

For nearly three decades the known Ramanujan graphs came only in degrees of the form prime plus one, a fingerprint of their number-theoretic origin. Marcus, Spielman and Srivastava proved in 2015 that bipartite Ramanujan graphs exist in every degree, by a genuinely new argument.³ The moral survives translation: the extremal object of network engineering was found waiting inside pure mathematics, name and all.