In Highly Connected Networks, There’s Always a Loop
Nico Roper/Quanta Magazine
Introduction
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.
Many graphs have such cycles. But in others, no matter how hard you try to find a Hamiltonian cycle, you’ll end up stuck: Maybe you’ll get trapped in an isolated bubble of the graph, with no way to visit all the points, or maybe you’ll be forced to retrace your steps.
Merrill Sherman/Quanta Magazine
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 Millennium Prize Problems, netting a million dollars from the Clay Mathematics Institute.)
Two Hamiltonian cycles are depicted at left and center, while on the graph to the right, it’s impossible to find such a cycle.
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.
In Search of Cycles
Krivelevich and Sudakov’s conjecture punctuated a long series of attempts to untangle the conditions that would guarantee a Hamiltonian cycle. Back in 1952, Gabriel Dirac, a Danish mathematician (and stepson of the famous physicist Paul Dirac), proved that every graph with n points, or nodes, where each node is connected to at least n/2 others contains a Hamiltonian cycle. But this is a lot of lines (more commonly called edges). Over the years, mathematicians worked to reduce the number of edges Hamiltonian graphs had to have. In 1976, the Hungarian mathematician Lajos Pósa proved that certain graphs built by randomly drawing edges were virtually guaranteed to contain Hamiltonian cycles. By 2001, Krivelevich and Sudakov, together with two other colleagues, as well as another competing group, had proved similar results about a different class of graphs.
Krivelevich and Sudakov thought they knew why graphs made at random were likely to contain a Hamiltonian cycle. Random graphs have two key properties. The first property concerns what happens if you examine two large, nonoverlapping groups of nodes within the graphs. In a random graph, it’s very likely that there will be at least one edge connecting the groups.
The second property involves small groups of nodes. Take a small group of nodes, and call it A. Now enlarge it by adding every node that’s connected to something in A. Mathematicians call this larger group the “neighborhood” of A. In random graphs, the neighborhood of A is likely to be far larger than A itself. So mathematicians say that A “expands” to a large neighborhood.
Graphs with these two properties — where large groups of nodes are likely to share an edge, and where small groups of nodes expand into much larger groups — are called expander graphs. If the neighborhood of A is c times bigger than A, then the graph is called a c-expander.
Though many random graphs end up being expanders, expanders don’t have to be random. Rather, an expander “has the properties of a random graph without needing randomness,” said Tom Gur of the University of Cambridge.
Because of the conditions they must satisfy, expander graphs are highly interconnected, meaning you can get from one part of the graph to another in relatively few steps, even when there aren’t many edges. Expanders, Gur said, manifest the tension between connectivity and sparsity.
Early work on expander graphs was inspired by networks of neurons, and the graphs have shown up in other domains as well. Some large online social networks are expanders, and expanders can be used to build efficient error-correcting codes and improve the accuracy of random algorithms.
In their 2002 paper, Krivelevich and Sudakov proved that certain types of expanders have Hamiltonian cycles. They thought that expanders more generally also have such cycles, but they couldn’t prove it. “We firmly believed that the conjecture should be true, and we also pretty firmly believed that [proving] the conjecture would be very, very hard,” Krivelevich said.
Over the next two decades, Sudakov returned to the problem occasionally but didn’t make much progress. That changed in March 2023, when Sudakov, his student David Munhá Correia, and Stefan Glock of the University of Passau improved on the 2002 result, showing that a slightly larger class of expander graphs must have Hamiltonian cycles. “We generated many ideas and at some point realized that they can be combined in the right way,” Sudakov said. “David and Stefan were very enthusiastic about the problem all the time and not willing to give up.”
The following month, Richard Montgomery from the University of Warwick and Alexey Pokrovskiy of University College London came to visit Sudakov in Zurich. Montgomery had tried to prove Sudakov and Krivelevich’s conjecture as part of his doctorate at Cambridge in the early 2010s, but had given up because he thought he didn’t have the right tools to tackle the problem. With the recent progress made by Sudakov, Munhá Correia and Glock, Montgomery thought it was worth another attempt. “I suggested this to work on, without necessarily any strong sense that we would make any significant progress,” Montgomery said.
Over the next couple of weeks, Montgomery, Sudakov and Pokrovskiy came up with a strategy. They used a technique called Pósa rotation to amass a collection of long paths, hoping to eventually connect those paths into a Hamiltonian cycle. Montgomery returned home to Warwick without a proof, but with newfound optimism. “We had this feeling that eventually, one way or another, we should have the right ideas to get the result,” Sudakov said.
Near the end of 2023, Munhá Correia and a recently graduated student of Sudakov’s, Nemanja Draganić, told Sudakov that they had also been working on the conjecture. Munha Correia and Draganić had an idea for connecting paths into a Hamiltonian cycle using a contraption called a sorting network, which they’d come across in a November 2023 paper. “We sat together and realized that all these ideas could be put together to, probably, solve the problem,” Munhá Correia said.
A sorting network is a graph that contains two matching sets A and B. The sorting network is structured so that no matter how you pair points in A with points in B, it’s possible to find nonintersecting paths that connect each point in A with its corresponding point in B. “You tell me how you enter, and you tell me how you want to exit,” Sudakov explained. “The sorting network has a property that there is a path from every vertex to the destination.”
The paper from November contained a proof that particular types of expander graphs must contain sorting networks. Draganić, Montgomery, Munha Correia, Pokrovskiy, and Sudakov realized that if they could combine sorting networks with Pósa rotation, they would be able to prove the conjecture. They used the techniques of the November 2023 paper to show that expander graphs also must contain sorting networks. Then, by taking the sets A and B to be the endpoints of the paths they’d created using Pósa rotation, they saw that they could tie their collection of long paths into a Hamiltonian cycle. “We crystallized all the key concepts which we need for the proof,” Sudakov said.
By February, the group had written up their paper. It proved not only the original 2002 conjecture of Krivelevich and Sudakov, which had used a narrower definition for expanders, but something even stronger: Any c-expander has a Hamiltonian cycle, as long as c is big enough. Their method also generated an actual Hamiltonian cycle, rather than proving abstractly that one existed. Sudakov forwarded the draft to Krivelevich. “I was rather doubtful we’d see it solved in our lifetime,” Krivelevich responded.
The new proof solves several questions about Hamiltonian cycles. It proves, for instance, that certain types of graphs that have to do with groups, called Cayley graphs, must have Hamiltonian cycles. But it isn’t the last word. Mathematicians could still try to find the lowest possible bound on c, the expansion factor, and perhaps prove that a broader class of graphs, called tough graphs, must contain cycles. (Sudakov said that though this is an aspiration, a proof is “nowhere close,” and he cautioned that “there is no good evidence that the conjecture is even true.”)
Gur, who wasn’t involved in the work, said it establishes “a fundamental connection between two objects which are central to computer science.” That connection, he said, will lead to important applications. “I don’t know what form it will take. It just seems like this is bound to be useful.”
