A 53-Year-Old Network Coloring Conjecture Is Disproved
Olena Shmahalo/Quanta Magazine
Introduction
A paper posted online last month has disproved a 53-year-old conjecture about the best way to assign colors to the nodes of a network. The paper shows, in a mere three pages, that there are better ways to color certain networks than many mathematicians had supposed possible.
Network coloring problems, which were inspired by the question of how to color maps so that adjoining countries are different colors, have been a focus of study among mathematicians for nearly 200 years. The goal is to figure out how to color the nodes of some network (or graph, as mathematicians call them) so that no two connected nodes share the same color. Depending on the context, such a coloring can provide an effective way to seat guests at a wedding, schedule factory tasks for different time slots, or even solve a sudoku puzzle.
Graph coloring problems tend to be simple to state, but they are often enormously hard to solve. Even the question that launched the field — Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering).
The problem tackled in the new paper seemed, until now, to be no exception to this rule. Unsolved for more than 50 years, it concerns tensor products — graphs made by combining two different graphs (call them G and H) in a specific way. The tensor product of G and H is a new, larger graph in which each node represents a pair of nodes from the original graphs — one from G and one from H — and two nodes in the tensor product are connected if both their corresponding nodes in G and their corresponding nodes in H are connected.
Suppose you’re a music teacher who wants to find good duet pairings for the fifth grade concert. You could make a graph whose nodes are the students, with a link between each pair who get along well. And you could make a second graph in which each node is a different musical instrument, with a link between two instruments if you have sheet music for a duet that features them. The tensor product of these two graphs would have one node for each possible pairing of a student and an instrument (say, Alicia on the trombone), and two nodes will be linked whenever the two students in question work well together and the two instruments are compatible.
In 1966, Stephen Hedetniemi, now a professor at Clemson University in South Carolina, conjectured in his doctoral dissertation that the minimum number of colors required by a tensor product is the same as the number of colors required by one of its two constituent graphs — whichever of the two numbers is smaller. “It’s a major conjecture in graph theory,” said Gil Kalai of the Hebrew University of Jerusalem. “Many people tried to think about it.”
Over the decades, mathematicians amassed an array of evidence, some of which pointed to the conjecture being true and some to it being false. Mathematicians had different guesses about which possibility would eventually prevail. But everyone seemed to agree, at least, that the problem was a hard one.
“I personally thought the conjecture should be true, because a lot of smart people had looked at it and should have found a counterexample” if one existed, said Anthony Bonato of Ryerson University in Toronto.
But now the Russian mathematician Yaroslav Shitov has come up with a simple way to construct such counterexamples: tensor products that require fewer colors than either of their two constituent graphs. The proof is “elementary, but ingenious,” said Pavol Hell of Simon Fraser University in Burnaby, Canada.
Tensor graphs are closely related to questions of how different graphs can be mapped into each other, and in that realm of mathematics, Hedetniemi’s conjecture was perhaps the biggest open problem, Hell said. “It’s an important breakthrough.”
Colorful Gatherings
To get a feel for the kind of information you can glean from coloring a tensor graph, imagine that you plan to invite friends to your country estate over a series of weekends. Like a good host, you want to assemble people who will enjoy each other’s company.
You know that some of your friends have jobs that they can instantly bond over, while others do not. Likewise, you know that each friend has a hobby — another way in which guests might find shared interests. You figure the dance teacher who plays the cello might enjoy talking shop with the yoga instructor who plays tennis, or discussing music with the maple syrup farmer who plays the piano, but might be hard-pressed to slip into conversation with the political scientist who collects stamps. You want each pair of guests at any gathering to be able to find some mutual area of interest, whether through jobs or hobbies, and you’re wondering how many gatherings you need to host before you’ve invited everyone on your guest list.
You could represent the relationships between different jobs with a graph whose nodes are the jobs, with links connecting any two jobs that are not conducive to shared shop talk. (This might feel backward, but connecting these nodes makes sense in the context of graph coloring, since we’ll ultimately use the colors to separate these problematic pairings.) Likewise, you could make a graph whose nodes are the different hobbies and connect two hobbies whenever they are incompatible.
The tensor product of these two graphs will have a node for each job-hobby pairing, and two nodes are connected if the two jobs and the two hobbies are both incompatible — exactly the situation you want to avoid at your weekend retreats. Now, if you can color the nodes of the tensor product so that connected nodes are different colors, that will give you a way to form guest lists for different weekends: You can invite the people corresponding to the green nodes on the “green” weekend, the red nodes on the “red” weekend, and so forth, with the assurance that incompatible guests will visit on different weekends. The number of colors you used tells you how many weekends to block off in your calendar.
One thing to notice from this example is that any valid coloring of the job graph carries over to the tensor product — you can simply color each job-hobby combo the same color you used for its job. Such a coloring results in gatherings in which each pair of guests is compatible based purely on their shared professional interests, regardless of their hobbies.
Likewise, any valid coloring for the hobby graph will carry over to the tensor product. Hedetniemi conjectured that whichever of the two carry-over colorings uses fewer colors is, in fact, the best possible way to color the tensor graph.
On the face of it, Hedetniemi’s conjecture seems improbable. After all, if you base your tensor coloring on a coloring of the job graph, you’re ignoring everything you know about your friends’ compatible hobbies, and potentially separating guests who would have gotten along just fine. If, instead, you combined all your information about jobs and hobbies, maybe you could get away with using fewer colors and enjoy some well-earned guest-free weekends.
Yet for more than 50 years, mathematicians could not find a single tensor product that needed fewer colors than one of its two constituent graphs. The conjecture is true, they were able to show, whenever one of the two constituent graphs requires four or fewer colors. And it is also true in the broader setting of “fractional” colorings, in which each node can be assigned a combination of colors — maybe 2/3 yellow and 1/3 green. (In terms of weekend house parties, this might correspond to having three different journalist friends who play tennis and inviting two of them on the “yellow” weekend and the third on the “green” weekend.)
These findings hinted that the conjecture might be true, but other findings suggested the opposite. Mathematicians have shown, for example, that Hedetniemi’s conjecture falls apart for graphs that require an infinite number of colors or for directed graphs, in which each link has a preferred direction. But even as mathematicians proved Hedetniemi’s conjecture in some broader contexts and disproved it in others, they couldn’t seem to resolve it in the setting Hedetniemi originally considered: finite, undirected graphs with non-fractional colorings.
“The general belief was that it’s likely to be true, but that it’s very hard, one way or another,” said Noga Alon of Princeton University.
Coloring Pages
Shitov has now sliced through these uncertainties with a crisp, simple demonstration that Hedetniemi’s conjecture is false. In a paper whose main argument boils down to just over one page of dense mathematics, he shows how to construct a type of tensor product that requires fewer colors than either of its constituent graphs.
Shitov starts by considering what happens when you combine a graph G with one of its “exponential” graphs to form a tensor product. An exponential graph has one node for each possible coloring of G with some fixed number of colors (here, we’re allowing every possible coloring, not just colorings in which connected nodes are different colors). If the graph G has, say, seven nodes and our palette has five colors, then the exponential graph has 57 nodes — hence the name “exponential.”
Returning our attention to colorings in which connected nodes are supposed to be different colors, we have no guarantee that the five colors in our palette will be sufficient to color the graph G; likewise, they might not be enough to color the 57-node exponential graph. But mathematicians have long known that there is one graph that these five colors are sufficient to color: the tensor product made from G and its exponential graph.
All exponential graphs, in fact, have this property: The tensor product that combines the exponential graph with the graph it was built from can be colored with exactly the same number of colors as in the original palette used to make the exponential graph. Shitov disproved Hedetniemi’s conjecture by showing how to build a graph G such that both G and its exponential graph require more colors than are in that palette.
Hedetniemi has declared himself “absolutely delighted” to have his conjecture resolved after so many decades. Shitov’s proof “has a certain elegance, simplicity and definitive quality to it,” he wrote in an email.
The new counterexample is clever and inventive, mathematicians say, and it doesn’t require any complex, cutting-edge mathematical tools. “To a graph theorist, you can explain the construction in two sentences,” Kalai said.
Why such an argument was overlooked for more than 50 years is a mystery to mathematicians. “Sometimes, a little gem is covered by leaves,” Hell said. “[Shitov] just managed to understand it more deeply than anybody else.”
Shitov’s graphs are gargantuan: While he has not calculated precisely how large they are, he estimates that the graph G probably has at least 4100 nodes, and the exponential graph at least 410000 nodes — a number vastly larger than the estimated number of particles in the observable universe.
Then again, “gargantuan” is in the eye of the beholder. To Shitov, his counterexample is “not extremely huge,” he said. “There are counterexamples in mathematics [compared to] which this is a really tiny thing.”
And while you’re unlikely to invite 410000 guests to your country home, Shitov’s work doesn’t rule out the existence of much smaller counterexamples. Now that mathematicians know Hedetniemi’s conjecture is false, the natural next question is just how false it is: how many fewer colors a tensor product might require than its constituent graphs do, and how few nodes and links such counterexamples can have.
Meanwhile, the new paper contains an important lesson for mathematicians, Alon said. “Sometimes, the reason that a conjecture is very hard to prove is simply that it is false.”
