In highly connected networks, there’s always a loop
Mathematicians show that graphs of a certain common type must contain a route that visits each point exactly once.
As mathematical abstractions go, graphs are among the simplest. Scatter a bunch of points in a plane. Connect some of them with lines. That’s all a graph is. And yet they are incredibly powerful. They can be used to attack a wide variety of problems, from modeling neurons in the brain to routing delivery trucks on the roads. Within math, they can be used to categorize important algebraic objects called groups, to describe knots, and in myriad other ways.
One of the central problems in graph theory is finding routes that visit each point in a graph exactly once before returning to their starting point. These routes are called Hamiltonian cycles, after the 19th-century mathematician William Rowan Hamilton.
For small graphs, like the one above, it's relatively easy to find out if a Hamiltonian cycle exists by trial and error. In this case, it doesn’t.
But if you start considering graphs with hundreds or thousands or millions of points and lines, that task becomes very difficult. There's no known efficient algorithm for determining if a given large graph contains a cycle or not. If someone were to find such an algorithm, it would produce solutions to a vast collection of problems in mathematics and computer science. (Such an algorithm would also solve one of the six remaining external pageMillennium Prize Problems, netting a million dollars from the Clay Mathematics Institute.)
So instead of trying to produce a general algorithm for finding Hamiltonian cycles, some mathematicians have focused on the easier problem of proving that particular types of graphs contain such cycles. In 2002, Michael Krivelevich of Tel Aviv University and Benny Sudakov, now at the Swiss Federal Institute of Technology Zurich, conjectured that an important class of graphs called expander graphs all contain Hamiltonian cycles. In February, together with four other mathematicians, Sudakov succeeded in proving the conjecture he'd first ventured over two decades earlier.
Read the full article in external pageQuanta Magazine
The work was carried out in collaboration with Nemanja Draganić and David Munhá Correia, two former doctoral students of Benny Sudakov, as well as with Richard Montgomery and Alexey Pokrovskiy, who visited the department in spring 2024 as guests of the FIM.