Russian mathematician refutes the 53-year-old hypothesis about the coloring of networks

Only three pages were required for the Russian mathematician to describe a method of coloring networks of a certain type that exceeded the expectations of experts

A 53-year-old hypothesis regarding the best way to assign colors to network nodes is refuted in an online paper . The work on only three pages shows the existence of methods for coloring certain colors that have exceeded all expectations of experts.



Tasks for coloring nets [ see chromatic number / approx. perev. ], inspired by the question of such coloring of maps, in which neighboring countries have different colors, have been in the focus of research by mathematicians for almost 200 years. The task is to understand how to color the nodes of a certain network (or graph , what their mathematicians call them) so that any two connected nodes have different colors. Depending on the context, this coloring can provide an effective way of seating guests at a wedding, arranging production tasks for free time intervals, or even solving sudoku .



Graph coloring tasks are often easy to formulate, but incredibly difficult to solve. Even in search of an answer to the question from which this entire field of research began, are four colors enough for coloring any map ? - It took more than a hundred years (if you are interested, the answer is yes).



The task considered in the new work, until now, was not considered an exception. It could not be solved for more than 50 years, and it concerns tensor products - graphs made up of a special combination of two different graphs (let's call them G and H). The tensor product of the graphs G and H is a new, larger graph, each vertex of which denotes a pair of vertices of the original graphs - one from G and one from H - while two vertices of the tensor product are connected if both their corresponding vertices in G and their corresponding vertices in H.



Suppose you are a music teacher and you need to find good duo couples for a fifth year concert. You can make a graph, the vertices of which will be students, and the bonds between the pairs will indicate the presence of good relations between them. Then you can make a second graph in which each node will indicate different musical instruments, and the connection between them is the presence of music sheets for a duet of these two instruments. In the tensor product of these two graphs, there will be one vertex for each possible union of the student and the instrument (say, Alice and trombone), and the two vertices will be connected if two students work well together, and the two instruments are compatible.



In 1966, Stephen Hedetniemi , now a professor at Clemson University in South Carolina, suggested in his doctoral dissertation that the minimum number of colors needed to color a tensor product is the smallest of the two colors needed to color either of the two graphs . “This is one of the main hypotheses in graph theory,” said Gil Kalai of Hebrew University in Jerusalem. “A lot of people tried to ponder her.”



Over the past decades, mathematicians have gathered a mountain of evidence, some of which talked about the truth of the hypothesis, and some - about its falsity. Different mathematicians had different assumptions about which option would ultimately win. But everyone agreed that at least it was a difficult task.



“Personally, I thought this hypothesis was true, since a huge number of smart people studied it, and would have to come up with a counterexample,” if that existed, said Anthony Bonato of Ryerson University in Toronto.



And so the Russian mathematician Yaroslav Nikolayevich Shitov came up with a simple way to create counterexamples, tensor works that require fewer colors than either of the two graphs that make them up. The evidence came out “elementary but brilliant,” said Pavol Hell from Simon Fraser University in Burnaby, Canada.



Tensor graphs are closely related to questions about mappings of different graphs onto each other, and in this area of ​​mathematics, the Hedetniemi hypothesis was probably the largest open problem, Hell said. “This is a major breakthrough.”

Colorful hangouts

To imagine what information can be extracted from coloring the tensor graph, imagine that you are going to invite your friends to your suburban estate every weekend. And, as a good host, you want to gather people who will enjoy each other's company.



You know that some of your friends will be able to make friends quickly on the basis of work, while others will not. You also know that your friends have a hobby - another way through which guests can find common interests. You speculate that a violin dancing teacher can have a good time talking with a yoga instructor playing tennis or discussing music with a farmer who produces maple syrup and plays the piano, but probably not about him than he will speak with a political scientist collecting stamps. You want every couple of guests to be able to find some common interests at any weekend, be it a job or a hobby, and you are wondering how many gatherings you need to arrange to sort out all the guests from the list.





Yaroslav Shitov discovered a counterexample of the 53-year-old Hedetniemi hypothesis from graph theory



You could imagine the relationship of various types of work in the form of a graph, the nodes of which will be the work, and any two jobs will be connected by edges, between which, most likely, it will not be possible to find common topics for conversation (this approach may seem turned inside out, however, in the context of coloring graphs such a connection of vertices makes sense, since we will use colors to separate these problematic pairs). You could also make a graph, the vertices of which are different hobbies, and combine all the incompatible ones.



The tensor product of these two graphs will have nodes for each work-hobby pair, and the two vertices will be combined if both work and both hobbies are incompatible - this is exactly the situation that you want to avoid on the weekend. If you can color the vertices of the tensor product so that the vertices connected by the ribs have different colors, this will give you a way to create guest lists for different weekends: you can invite people corresponding to green vertices on the “green” weekend, red vertices on the “red” ", And so on, and be sure that incompatible guests will be on the lists on different weekends. The number of colors you use will tell you how many days off you will need to take on the calendar.



It follows from this example that any valid coloring of the work graph can be transferred to the tensor product — you can simply color each work-hobby combination in the same color that you used for the work. Such a coloring will lead to the fact that at the gatherings each couple of guests will be compatible exclusively according to their professional interests, regardless of their hobby.



And vice versa, any admissible coloring of the hobby graph is also transferred to the tensor product. Hedetniemi suggested that the best way to color a tensor graph would be to have one of the original graphs have a minimal number of colors.



At first glance, the Hedetniemi hypothesis seems unlikely. After all, if you base tensor coloring on the coloring of the working graph, you ignore everything that you know about your friends ’compatible hobbies and potentially share guests who get along with each other. If you combine all the information about work and hobbies, you may be able to use fewer flowers and enjoy a well-deserved weekend without guests.



And yet, for more than 50 years, mathematicians could not find a single tensor product whose coloring would require fewer colors than any of its constituent graphs. They were able to prove that the hypothesis is true if no more than four colors were required to color one of the two graphs. It is also true in the more general case of "fractional" colorings, when each vertex can be assigned a combination of colors - for example, 2/3 yellow and 1/3 green. (In terms of weekend gatherings, this may correspond to a situation where there are three journalists on your friends list, one of whom plays tennis, and you invited two of them to the “yellow” weekend, and the third to the “green”).



These findings suggested that the hypothesis could be true, but others said the opposite. For example, mathematicians have shown that the Hedetniemi hypothesis falls apart for graphs that require an infinite number of colors for coloring, or for directed graphs whose edges have preferred directions. But, despite the fact that mathematicians proved the Hedetniemi hypothesis for some cases, and refuted it for others, they could not solve the problem in the area that Hedetniemi himself originally considered: finite undirected graphs with integer coloring.



“Everyone generally thought it was true, but it was difficult to prove or disprove it,” said Noga Elon from Princeton University.

Coloring Pages

Shitov broke all these uncertainties with a clear and simple demonstration of the falsity of the Hedetniemi hypothesis. In the work, the main proof of which fits on one page, stuffed with mathematics, he shows how to create a special type of tensor product, which requires less colors to paint than for any of its components.



Shitov begins his work by observing what will happen if we combine the graph G with one of its exponential graphs and obtain their tensor product. The exponential graph has one node for each of the possible colorings G with a certain fixed number of colors (all possible colorings are allowed, not only those for which the connected vertices have different colors). If the graph G, for example, has 7 vertices, and there are 5 colors in our palette, then the exponential graph will have 5 ⁷ vertices - which is why it is called exponential.





Stephen Hedetniemi's hypothesis about the minimum number of colors for coloring a tensor product of graphs has remained unconfirmed for more than 50 years



If we return to the coloring option, in which the connected vertices must be of different colors, then we can’t guarantee that the five colors of our palette will be enough to color the graph G, and in the same way they might not be enough to color the exponential graph with 5 ⁷ vertices . However, mathematicians have long known that there is one graph for which five colors are sufficient: it is a tensor product consisting of G and its exponential graph.



In fact, all exponential graphs have this property: a tensor product that combines an exponential graph with the graph from which it was created can be colored with exactly the same number of colors as the original graph. Shitov refuted the Hedetniemi hypothesis, showing how it is possible to create such a graph G that more colors are needed for coloring both it and its exponential graph.



Hedetniemi stated that he was “completely delighted” with the resolution of the situation with his hypothesis after so many decades. Shitov’s evidence “has a certain elegance, simplicity and sheer quality,” he wrote in an email.



The new counterexample turned out to be cunning and inventive, mathematicians say, and it doesn’t need complex advanced mathematical tools. “For a graph theory specialist, this design can be explained in two sentences,” Kalai said.



Why no one has noticed this argument for more than 50 years is a mystery to mathematicians. “Sometimes a little gem hides under a pile of foliage,” Hell said. “Shitov simply managed to understand this question more deeply than everyone else.”



Shitov’s graphs are gigantic: he did not calculate their exact size, but estimates that graph G is likely to have about ^4,100 vertices, and exponential graphs will have at least ^4,000 vertices, that is, much more than the approximate number of elementary particles in observable universe [ about 10 ⁸⁰ / approx. perev. ].



But, of course, it all depends on the observer. Shitov believes that his counterexample “is not so huge. In mathematics, you can find counterexamples, in comparison with which this one will be very tiny. "



And although you are unlikely to be able to invite ^4,000 to your country house, Shitov's work does not reject the existence of counterexamples of much smaller size. But now that mathematicians know that the Hedetniemi hypothesis is false, the natural question is how exactly it is false: how fewer colors can be needed to color a tensor product compared to its constituent graphs, and what is the minimum number of nodes and edges such counterexamples can have?



Meanwhile, Elon said that the new work contains an important lesson for all mathematicians: “Sometimes the reason that a hypothesis is so difficult to prove is that it is false.”