Mathematicians Answer Old Question About Odd Graphs
The highlighted part of this graph forms a subgraph in which all the vertices have an odd number of connections with each other. Mathematicians now know the minimum size of a subgraph guaranteed to have this property in any graph.
Samuel Velasco/Quanta Magazine
Introduction
For decades, mathematicians have debated a simple question about graphs and the number of connections they have. Now, using arguments an undergraduate math student could have come up with, Asaf Ferber of the University of California, Irvine and Michael Krivelevich of Tel Aviv University have finally provided the answer in the form of a proof posted in March.
“It’s a bit of a surprise, at least for me, that such a combination of clever but basic arguments suffice[d],” said Yair Caro, a mathematician at the University of Haifa.
Graphs are collections of vertices (dots) connected by edges (lines). After hundreds of years of study, mathematicians are still investigating their basic properties. One concerns the “parity” of a graph’s vertices, meaning whether they are connected to an odd or even number of other vertices.
Over the last century mathematicians have proved a number of basic results related to parity. In the 1960s Tibor Gallai proved that it’s always possible to split the vertices of a graph into two groups, or subgraphs, such that all the vertices within each subgraph have an even number of connections with each other (ignoring their connections to vertices outside the group) — a property called even “degree.”
Around the same time he observed that it’s also always possible to split the vertices in a graph into two subgraphs such that the vertices in one all have even degree and the vertices in the other all have odd degree.
The final option, however, is impossible: There’s no way to split every graph into two subgraphs such that all the vertices within each have odd degree. We know this because in the 1730s Leonhard Euler, perhaps the most prolific mathematician in history, proved that if a group of vertices all have odd degree, then the group must have an even number of vertices. If you’ve split the vertices of a graph into two subgraphs, and all the vertices within each have odd degree, each subgraph must have an even number of vertices and the original unsplit graph can therefore also only have an even number of vertices (because the sum of two even numbers is always even). Which means if the original graph has an odd number of vertices, there’s no way to do the splitting.
Given the fact that you can’t always split a graph into two subgraphs of odd degree, the next natural question becomes: What’s the largest proportion of the vertices in a graph that you can always be assured will have odd degree?
“You cannot do odd-odd, and therefore you need to settle for next best thing, which is, let’s do odd with a substantial portion of vertices,” said Krivelevich.
Michael Krivelevich of Tel Aviv University (top) and Asaf Ferber of the University of California, Irvine, have shown that at least $latex \frac{1}{10,000}$ of the total vertices of any graph form a subgraph in which all vertices have an odd number of connections with each other.
Michael Krivelevich of Tel Aviv University (left) and Asaf Ferber of the University of California, Irvine, have shown that at least $latex \frac{1}{10,000}$ of the total vertices of any graph form a subgraph in which all vertices have an odd number of connections with each other.
MFO; Liam Hardiman
To cement the question, consider a simple example: a graph with three connected vertices in the shape of a triangle. You can isolate any two vertices and see that they share an odd number of connections (1) with each other. Put another way, it’s possible to identify a subgraph of the triangle containing two-thirds of its total vertices, in which all the vertices have odd degree.
About 50 years ago, mathematicians predicted that for graphs of a given size, there is always a subgraph with all odd degree containing at least a constant proportion of the total number of vertices in the overall graph — like $latex \frac{1}{2}$, or $latex \frac{1}{8}$, or $latex \frac{32}{1,007}$. Whether a graph has 20 vertices or 20 trillion, the size of the subgraph should always meet or exceed the same ratio.
“The point is, your original graph can be larger and larger and we’re still able to maintain the same proportion,” said Krivelevich.
But for years no one could find such a specific ratio. In the early 1990s Caro found a ratio that fluctuated with the size of the graph, not a constant one. He proved that if you have N vertices in a graph, there’s a subgraph containing at least $latex \frac{1}{\sqrt{N}}$ of them in which all the vertices have odd degree. Two years later, Alex Scott improved that result to $latex \frac{1}{log N}$, which is much closer to a constant ratio than Caro’s result, but not all the way there.
“It was close, but no cigar,” said Scott, now a professor at the University of Oxford.
Progress on the problem languished for almost 30 years until February 2020, when Krivelevich, Ferber’s former graduate adviser, traveled to California to meet with him.
Ferber had recently revisited the problem about odd graphs, spurred by a tangentially related question one of his colleagues had asked him. He brought the problem up with Krivelevich and they started working through a strategy they’d develop over the next six months.
Their basic approach — which others before them had also followed — was to sort graphs into three types: “sparse” graphs, where there are lots of vertices that are connected to few other vertices, “dense” graphs with a single vertex connected to many others (relative to the total number of vertices in the graph), and graphs in the middle, with neither of these qualities. Previous work from the 1990s made the sparse and dense cases easy to understand. The hardest part was understanding the middle ground.
“The question is, what are you doing in between,” said Ferber.
They came up with a procedure that allowed them to prove that if a graph is neither sparse nor dense, it must have another quality: many small subgraphs that are dense within themselves (though not dense relative to the overall graph) and which are completely disconnected from each other. Proving this last point, that the many small dense subgraphs aren’t connected to each other, was one of the trickiest parts of the project.
“To show there are no edges between them is quite a pain,” said Ferber.
Ferber and Krivelevich established that these many small, dense subgraphs can be joined together to create a larger subgraph in which all vertices have odd degree. Now they’d covered all the possibilities — sparse graphs, dense graphs and graphs in between — and showed that they all necessarily contain odd subgraphs of a certain minimum size.
After a false start in 2020, when Scott let them know of a critical error they were able to circumvent, Ferber and Krivelevich posted the final result in late March 2021. They proved that every graph contains a subgraph, accounting for at least $latex \frac{1}{10,000}$ of its vertices, in which all the vertices have an odd number of connections with each other. Finally, they had their constant fraction.
(The actual proportion they arrived at was slightly larger, but they rounded it to $latex \frac{1}{10,000}$ for aesthetic reasons. “Imagine if we would write $latex \frac{1}{9,456}$ or some other ugly expression,” Ferber said.)
From here, there are at least two ways to go. The first is to try and improve the fraction. It’s very likely that the proportion of vertices that must have an odd number of connections is greater than $latex \frac{1}{10,000}$. In the 1990s, Scott speculated it might be as many as $latex \frac{2}{7}$, and future work could chase that number.
The second involves a host of related questions that have taken on new life following this work.
Mathematicians want to understand the sizes of collections of vertices with other numeric properties in common — like large groups of vertices, none of which is connected to a number of other vertices that’s evenly divisible by 3 or 5. It’s not clear whether those situations can be characterized by simple fractions too, but it’s encouraging that the proportion of vertices with odd degree can be.
“[The proof] suggests you should hope for a nice answer there as well,” said Scott.
Correction: May 19, 2021
Michael Krivelevich met in person with Asaf Ferber in 2020, not 2019.
