According to mathematical legend, Peter Sarnak and Noga Alon made a bet about optimal graphs in the late 1980s. They’ve now both been proved wrong.

It started with a bet.

In the late 1980s, at a conference in Lausanne, the mathematicians Noga Alon(opens a new tab) and Peter Sarnak(opens a new tab) got into a friendly debate. Both were studying collections of nodes and edges called graphs. In particular, they wanted to better understand a paradoxical type of graph, called an expander, that has relatively few edges but is still highly interconnected.

At issue were the very best expanders: those that are as connected as they can be. Sarnak proposed that such graphs are rare; he and two collaborators would soon publish a paper that used complicated ideas from number theory(opens a new tab) to build examples, and he argued that any other constructions would be similarly difficult to achieve. Alon, on the other hand, was banking on the fact that random graphs often display all sorts of optimal properties. He thought that these extremely good expanders would be common — that if you randomly select a graph from a large bucket of possibilities, you can practically guarantee it to be an optimal expander.

Today, Alon and Sarnak are colleagues at Princeton University. The details of the bet have become hazy in the intervening 35 years. “It was not extremely serious,” Alon recalled. “We didn’t even agree on what we are betting.”

Still, the legend persisted, a subtle nudge to mathematicians to find out who was right. In December, by tapping into a crucial phenomenon in physics — and pushing it to its limits — three mathematicians finally issued a verdict(opens a new tab). Alon and Sarnak were both wrong.

...read more at quantamagazine.org