New Proof Settles Decades-Old Bet About Connected Networks
1 min read
Summary
Mathematicians have long studied “expander” graphs, which have many nodes but few edges and are highly interconnected.
In the late 1980s, the mathematicians Peter Sarnak and Noga Alon made a bet about the prevalence of a particular kind of optimal expander graph, which came to be known as Ramanujan graphs.
Recently, three mathematicians settled the 35-year-old bet using a concept from the study of random matrices.
Their proof shows that Sarnak and Alon were both wrong: The answer to their wager is that Ramanujan graphs are neither rare nor common, appearing in about 70% of all regular graphs.
Sarnak and Alon both say they’re relieved to have the question resolved, though Alon maintains that he was “a little bit more correct” because his estimate was higher.
