New Proof Settles Decades-Old Bet About Connected Networks

a year ago

Mathematicians Noga Alon and Peter Sarnak made a bet in the late 1980s about the rarity of optimal expander graphs, known as Ramanujan graphs.
Expander graphs are highly interconnected networks with few edges, useful in modeling the brain, statistical analyses, and error-correcting codes.
The Alon-Boppana bound defines the limit for how well-connected a regular graph can be, with Ramanujan graphs reaching this optimal limit.
In 1988, Sarnak and collaborators used number theory to construct Ramanujan graphs, while Alon believed random graphs would commonly achieve this optimality.
A 2008 study suggested that some regular graphs are Ramanujan while others are not, complicating the resolution of the bet.
Horng-Tzer Yau, inspired by the universality conjecture in physics, worked on proving that random regular graphs' eigenvalues follow a predictable distribution.
In 2020, Yau and collaborators extended the universality conjecture to certain regular graphs, but a complete proof for all graphs was still needed.
With the help of Theo McKenzie and Jiaoyang Huang, Yau completed the proof in 2022, showing that 69% of random regular graphs are Ramanujan.
The result confirmed that both Alon and Sarnak were partially wrong, with Ramanujan graphs being neither rare nor common.
The proof also broadens the scope of the universality conjecture, opening new avenues for research in mathematics.

Hasty Briefsbeta