To certain mathematicians — Sarnak among them — the Alon-Boppana bound was an entrancing challenge. Could they construct graphs, they wondered, that reached this limit?
Gambling on Randomness
In a landmark paper published in 1988, Sarnak, Alexander Lubotzky and Ralph Phillips figured out how to. Using a highly technical result in number theory by the Indian math prodigy Srinivasa Ramanujan, Sarnak and his collaborators produced regular graphs that achieved the Alon-Boppana bound. As a result, they called these optimal expanders “Ramanujan graphs.” (The same year, Grigorii Margulis used different but still highly technical methods to build other examples.)
“Intuitively, it seems like you might expect” the almost prohibitive difficulty involved in constructing Ramanujan graphs, said Ramon van Handel of the Institute for Advanced Study in Princeton, New Jersey. “It seems like the best possible graph should be very hard to achieve.”
But in mathematics, objects that are difficult to construct often turn out to be surprisingly common. “It’s a general phenomenon in this business,” van Handel said. “Any example you could visualize won’t have these properties, but a random example will.”
Some researchers, including Alon, believed that the same might apply to Ramanujan graphs. The herculean effort required to find these graphs, Alon thought, said more about the human mind than it did about abundance. This conviction led to Alon and Sarnak’s bet: Sarnak wagered that if you gathered up all regular graphs, a negligible proportion would be Ramanujan; Alon, that nearly all would be. Soon, rumors of Alon and Sarnak’s bet were floating around the community, even if memories of the moment differ.
“To tell you the truth, it’s more folklore,” Sarnak admitted. “I don’t actually remember the event.”
Decades later, in 2008, an analysis of large numbers of regular graphs and their eigenvalues suggested that the answer wasn’t clear-cut. Some of the graphs were Ramanujan, some were not. This only made figuring out the exact balance more daunting. When proving a property that applies to all graphs (or none), mathematicians have a large toolkit they can turn to. But to prove that some graphs are Ramanujan, while others are not — that takes precision, and graph theorists weren’t sure where this precision would come from.
It turned out that in a completely different area of mathematics, a researcher named Horng-Tzer Yau was figuring that out.
A ‘Crazy’ Vision
As graph theorists grappled with the implications of the 2008 study, Yau, a professor at Harvard University, was several years into his own obsession with eigenvalues. These eigenvalues came from a much broader class of matrices, whose entries are randomly generated — say, by flipping a coin or performing some other random process. Yau wanted to understand how a matrix’s eigenvalues might change depending on which random process you used.
The problem dated back to 1955, when the physicist Eugene Wigner used random matrices to model the behavior of nuclei in heavy atoms like uranium. By studying the eigenvalues of these matrices, he hoped to gain insight into how much energy the system had. Wigner soon noticed something strange: The eigenvalues of different random matrix models all seemed to exhibit identical patterns. For any random matrix, each eigenvalue is also random; pick a range of values, and it has some probability of falling in that range. But it didn’t seem to matter if a random matrix consisted of only 1s and −1s, or if its entries could be any real number. In each case, the probability that its eigenvalues would fall in certain ranges of values didn’t change.
The physicist Eugene Wigner observed surprisingly universal behavior in various random systems he was studying. Mathematicians have now extended the scope of that behavior.
Oak Ridge National Laboratory, U.S. Dept. of Energy
Wigner conjectured that the eigenvalues of any random matrix should always obey the same probability distribution. His prediction became known as the universality conjecture.
The idea was “crazy,” Yau said. “Many people didn’t believe what he was saying.” But over time, he and other mathematicians proved that the universality conjecture held up for many kinds of random matrices. Over and over again, Wigner was vindicated.
Yau now wanted to see how far he could push the conjecture. “I was trying to look for problems that can sort of go beyond our understanding of a standard matrix,” he said.
So in 2013, when Sarnak proposed that Yau study the eigenvalues of the matrices associated with random regular graphs, he accepted the challenge.
If Yau could prove that these eigenvalues obeyed the universality conjecture, he’d know their probability distribution. He could then use that information to calculate how likely it was that the second eigenvalue would reach the Alon-Boppana bound. In other words, he’d be able to give a definitive answer to Sarnak and Alon’s bet about what fraction of regular graphs are Ramanujan.
“[Sarnak] just kept poking me, ‘Can you do it?’” Yau said.
So he set out to.
Almost There
Many kinds of random matrices, including the ones that inspired Wigner’s conjecture, have nice properties that make it possible to compute the distribution of their eigenvalues directly. But adjacency matrices don’t have those properties.
Around 2015, Yau, along with his graduate student Jiaoyang Huang and two other collaborators, came up with a plan. First, they’d use a random process to tweak the entries in their adjacency matrix slightly, getting a new random matrix that exhibited the properties they needed. They’d then compute the distribution of eigenvalues for this new matrix and show that it satisfied the universality conjecture. Finally, they’d prove that the tweaks they made were too small to affect the original matrix’s eigenvalues — meaning that the original matrix also satisfied the universality conjecture.
