New Proof Settles Decades-Old Bet About Connected Networks

Summary

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.” After spending more than a decade studying the matrices associated with random graphs, Horng-Tzer Yau has settled a major problem about their behavior. Courtesy of Horng-Tzer Yau 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 late...