Theory at the Institute and Beyond, February 2025
by Nikhil Srivastava (senior scientist, Simons Institute for the Theory of Computing)
Expanders are sparse and yet highly connected graphs. They appear in many areas of theory: pseudorandomness, error-correcting codes, graph algorithms, Markov chain mixing, and more. I want to tell you about two results, proven in the last few months, that constitute a phase transition in our understanding of expanders.
Random graphs are Ramanujan with 69% probability
One way to quantify the expansion of a graph is via its adjacency spectrum. A \(d\)-regular graph is called Ramanujan if its nontrivial (i.e., other than \(d\)) adjacency eigenvalues are bounded in absolute value by \(2\sqrt{d-1}\). Alon and Boppana showed in 1986 that no infinite sequence of graphs can have nontrivial eigenvalues concentrated on a smaller interval, so Ramanujan graphs may be viewed as optimal spectral expanders as a function of \(d\).
The most important result about Ramanujan graphs is that they exist. Motivated by the Alon-Boppana bound, Lubotzky, Phillips, and Sarnak and independently Margulis famously constructed infinite sequences of Ramanujan graphs whenever \(d = p + 1\) for a prime number \(p\) in 1988. This is a gift that keeps on giving, as we will see below, albeit one whose proof very few of its recipients understand.
Until December 2024, that was the only known proof of the existence of Ramanujan graphs. Two results came close: Friedman’s theorem (and its improvements) that random \(d\)-regular graphs are almost Ramanujan with high probability, and the existence and construction of bipartite Ramanujan graphs (which are allowed to have an extra eigenvalue of -\(d\)) for all \(d\) via the interlacing families method. It remained mysterious whether the existence of Ramanujan graphs was a precious miracle or the consequence of some robust phenomena.
Huang, McKenzie, and Yau have shown that a random \(d\)-regular graph on \(N\) vertices is Ramanujan with probability approaching 69% as \(N\) \(\rightarrow\) \(\infty\). The fact that this probability does not approach 0 or 1 is strange in the context of the probabilistic method (as reflected in a bet of Noga Alon and Peter Sarnak) and rules out typical proof techniques like concentration inequalities. But it was anticipated about 20 years ago in a different context: the universality phenomenon in random matrix theory.
Universality is like the central limit theorem. It predicts (among other things) that the distribution of the top eigenvalue of an \(N\)\(\times\)\(N\) real symmetric random matrix with independent normalized entries should converge (after appropriate scaling) to a universal law, regardless of the details of the entries. That limit is the Tracy-Widom law, discovered in 1994. The TW law shows up in many contexts — as the top eigenvalue of Gaussian and Wigner random matrices, as the distribution of the length of the longest increasing subsequence in random permutations, and as the distribution of fluctuations in liquid crystal droplets which can be seen in experiments. It is surprising to me that something so deeply embedded in nature was discovered only 30 years ago, though the proposal of universality in random matrix theory goes back to Wigner in the 1950s (in the context of spacings of eigenvalues rather than top eigenvalues, which he used to model the energy gaps of heavy nuclei).
Numerical experiments by Novikoff, Miller, and Sabelli from around 2004 suggested that the extreme nontrivial eigenvalues of random \(d\)-regular graphs should have asymptotically independent Tracy-Widom fluctuations (which are of scale \(N^{-2/3}\)) centered near \(\pm\)\(2\sqrt{d-1}\). Conceptually, this would mean that the edge eigenvalue fluctuations of random \(d\)-regular graphs behave like those of Gaussian orthogonal ensemble (GOE) matrices. This is subtle because the same is definitely not true for sparse Erdős-Rényi graphs, whose extreme eigenvalues are dominated by high-degree vertices. Proving this rigorously would immediately imply a constant probability of being Ramanujan, a proof combining both concentration and anticoncentration of the extreme eigenvalues.
This is what Huang, McKenzie, and Yau achieve. Their approach is a variant of the “local relaxation flow” strategy for proving universality results, introduced by Erdős, Schlein, and Yau in 2009 and refined in dozens of papers since then (see also this book). Letting \(A\) denote the adjacency matrix of a random \(d\)-regular graph on \(N\) vertices, the three steps in this strategy are:
Rigidity: Prove that all of the eigenvalues are very close to their expected locations with high probability. Here, very close means a deviation of roughly \(N^{-1}\) for each eigenvalue inside the spectrum and roughly \(N^{-2/3}\) at the edge, which are indeed the true sizes of the fluctuations.
Smoothed analysis: Consider the matrix \(B = A + \sqrt{t}G\) where \(G\) is a normalized GOE matrix with \(G1 = 0\) (so that the top eigenvector is not disturbed) and \(t\) is roughly \(N^{-1/3}\). Show that the fluctuations of \(\lambda_2(B)\) converge to the TW law.
Comparison: Show that the fluctuations of \(\lambda_2(A)\) and \(\lambda_2(B)\) converge to the same distribution after scaling by \(N^{-2/3}\).
When I see a proof whose conclusion seems to allow no room for error, my instinct is to ask, “Where is the slack?” One place is the “roughly”s in Step 1. The way rigidity is used is: the eigenvalue distribution of \(B\) in Step 2 is governed by a stochastic differential equation called Dyson Brownian motion, and Step 1 gives control over the initial conditions for that SDE. It turns out that the SDE “equilibrates” fast enough so that even if the initial conditions are slightly off, the distribution after a small time forgets about this and follows the correct TW fluctuations, yielding the conclusion in Step 2.
It is of course still difficult to establish Step 1. This was done in an earlier version of the paper, which came out in April. A key idea there, which is standard in mathematical physics and underutilized in CS, is to access the random matrix \(A\) via its Stieltjes transform \(m_A(z): = (1/N)\mathrm{tr}{(zI - A)}^{-1}\) for complex numbers \(z\) close to the spectrum of \(A\). In this regime, you can’t simply expand \({(zI - A)}^{-1}\) in a power series and interpret its entries as counting walks. However, the entries of \({(zI - A)}^{-1}\) still satisfy a nice combinatorial recursion arising from the Schur complement formula. At a very high level, the proof is able to use this recursion in addition to the exchangeability of the random graph distribution (a surrogate for independence) to control \(m_A(z)\) very close to the spectrum, which implies rigidity.
It’s kind of weird to add a dense Gaussian matrix to the adjacency matrix of a sparse graph. It seems that doing so would destroy the combinatorial structure of the graph and preclude any further combinatorial arguments, which presumably are needed in Step 3. But this is beautifully not the case. The reason is that adding Gaussian noise to \(A\) corresponds roughly to a nice change of variables at the level of the Stieltjes transforms \(m_A(z)\) and \(m_B(z)\) (a fact that is related to free probability), so one is able to remember and use the combinatorial structure of the graph in the analysis of \(B\) in Step 3.
How does any of this affect computer science? Materially, it doesn’t for now. After all, random graphs are not explicit, and I don’t know any application where being almost Ramanujan isn’t as good as being exactly Ramanujan. But the quest for Ramanujan graphs has had many unexpected consequences. This result is a landmark in that quest, giving a new mechanism for their existence, and with new ideas that may be digestible to computer scientists. More broadly, some proofs change your idea of what can (ever) be proven. To me, this is one of them.
Vertex expansion beyond 50%
While Ramanujan graphs are great, they are not the answer to everything. It is an easy exercise to show that a random \(d\)-regular graph is likely to be a lossless expander, which means that every subset \(S\) of at most 1% of its vertices has at least 0.99\(d\)|\(S\)| neighbors (i.e., very close to the maximum of \(d\)|\(S\)| neighbors). Bipartite lossless expanders, and their cousin unique neighbor expanders, are useful in coding theory. People have wanted to construct them deterministically for decades, and I grew up being taught that this was one of the guiding problems of pseudorandomness.
In an influential 1995 paper, Kahale showed that Ramanujan graphs have vertex expansion at least 0.5\(d\). For a long time, people were stuck at this 50%. In fact, Kahale showed that there is an essential barrier at 50%: there are near-Ramanujan graphs that have vertex expansion at most 0.5\(d\). The way he did this was by taking a Ramanujan graph and embedding a small copy of \(K_{2,d}\) in it without perturbing the spectrum too much. This means that even near-perfect spectral expansion cannot certify lossless expansion (in fact, neither can perfect spectral expansion). More recently, Kunisky and Yu showed that it is likely computationally difficult to certify that a random graph is a lossless expander. In the absence of spectral and algorithmic certificates, it was unclear how to deterministically construct lossless expanders or even beat the 50% barrier.
Progress was made on the weaker notion of one-sided lossless expansion, in which sets \(S\) on just one side of a bipartite graph are required to expand. For about 20 years, the only construction of one-sided lossless expanders was a delicate recursive construction based on the zig-zag product due to Capalbo-Reingold-Vadhan-Wigderson. Then, in 2023, Golowich and independently Cohen, Roth, and Ta-Shma gave a simpler method, inspired by a new graph product introduced by Asherov and Dinur. They start with a big bipartite spectral expander and place small “gadget” lossless expanders (which can be found by brute force) on its neighborhoods in a particular way. The key is to show that every small set on one side of the big graph intersects many gadgets in a small fraction of their vertices, which then implies one-sided lossless expansion. Curiously, these papers for different reasons suggested deriving the big graph from the face-vertex incidences of a high-dimensional expander.
There isn’t space here to tell you what a high-dimensional expander is. But it is an object with an interesting mathematical history. The original Ramanujan graphs were Cayley graphs whose spectral gap followed from Deligne’s proof of the “Ramanujan conjecture” for certain 2 \(\times\) 2 matrix groups. By 2002, Lafforgue was able to show the Ramanujan conjecture for \(k\) \(\times\) \(k\) matrix groups, a result for which he was awarded the Fields Medal. Cartwright, Solé, and Zuk asked, based on purely aesthetic considerations: What combinatorial objects appear if you replace 2 × 2 matrices with \(k\) \(\times\) \(k\) matrices in the proof of Ramanujan graphs? The result was Ramanujan complexes, discovered by Lubotzky, Samuels, and Vishne in 2004. For over a decade, Ramanujan complexes remained a mathematical curiosity. They were the seed from which the field of high-dimensional expanders grew, eventually yielding some of the biggest breakthroughs in theoretical computer science of this century.
Coming back to graphs, Hsieh, Lin, Mohanty, O’Donnell, and Zhang finally broke through the 50% barrier in November, giving a deterministic construction of sparse bipartite graphs with two-sided vertex expansion near 60%. Their construction relies on a refined graph product introduced in 2023 by Hsieh, McKenzie, Mohanty, and Paredes, who constructed a weaker object called a two-sided unique-neighbor expander. Their main insight is that Ramanujan complexes have an unexpected combinatorial property that is extremely useful in combination with this graph product: roughly speaking, small subgraphs of the face-vertex incidence graph of a Ramanujan complex have a low density of triangles, which may be viewed as a strengthening of the fact that small subsets of Ramanujan graphs have low average degree. This is what ultimately enables them to get two-sided instead of just one-sided expansion. They note that improving their vertex expansion bound to ⅚ while preserving certain symmetries would imply a new construction of quantum LDPC codes, a worthy intermediate goal on the path to two-sided lossless expansion. (Interestingly, Chattopadhyay, Gurumukhani, Ringach, and Zhao recently gave a construction of non-sparse two-sided lossless expanders which were based on classical error-correcting codes.)
As it happens, it is still not known whether the original Lubotzky-Phillips-Sarnak/Margulis graphs are lossless expanders. Maybe Ramanujan graphs are the answer to everything, after all.