A research group has solved a mathematical problem that has been open for 63 years, proving an extension of the 'Four Color Theorem'

If it is possible to color a geographic map so that any two countries with a common border line are colored in a different color, using four colors at most? Regarding the maps, the answer is yes, but what about circles that do not overlap but can be launched?

In 1959 it was the renowned mathematician Gerhard Ringel who floated a question: What is the minimum number of colors needed to color a given collection of circles, so that two tangent circles are colored in different colors? This question remained open for over sixty years and occupied the best scientists in the field, until Prof. Shahar Samrodinsky from Ben-Gurion University of the Negev, together with international mathematicians, managed to answer the question. their conclusions will be published at the main international conference in the field and are already causing echoes in the scientific community.

Prof. Shahar Samrodinsky from the Department of Mathematics at Ben-Gurion University of the Negev, together with the researchers- Dr. Linda Kleist from Germany, Prof. Bartosh Walczak from poland, Dr. Chaya Keller from Ariel University andJames Davis from Canada, did not know each other and some of them had never even met, but precisely when they gathered in a virtual room for the purpose of solving open problems in computational geometry as part of a conference on the subject, they managed to solve a mystery that has remained open since 1959, the Ringel problem.

Ringel's problem is closely related to the 'Four Color Theorem', which occupied the best mathematicians for 150 years and more - is it possible to paint a geographical map so that all two countries with a common border line are colored in a different color, using a maximum of four colors? The question also came up in the context of coloring a collection of circles - is it possible to color circles (which do not overlap but can touch) in four colors so that two touching circles get a different color? This question arose in the middle of the 19th century and only in 1977 was the proof received that the answer is yes.

Ringel expanded the question by asking how many colors would be enough if the circles overlapped? He presented an example in which four colors are not enough but five are and asked whether five colors will always be enough for any collection of circles? If not, how many colors will be enough? The current breakthrough has revealed that the answer to the problem Ringel floated is infinity! The research group constructed a counterexample for each number of colors and proved that any finite number of colors is not sufficient. Such coloring problems have implications for many areas such as frequency allocation for cellular antennas, assignment of pilots to airline flights, assignment of work tasks to a machine and other diverse uses.

The mathematical solution combines two modern fields of mathematics: graph theory and Ramsey theory. Graph theory offers a model for networks of objects with matching between pairs such as social networks, neural networks, communication networks, and the like. Ramsey's theory describes situations in which there cannot be absolute chaos. In any large enough collection of objects (such as a large social network, pixels on a screen, a long text in the Hebrew language, or the position of stars in space) there will always be beautiful patterns that look as if they were drawn by a deliberate hand.

What makes the solution even more mysterious is the examples the researchers offered in the mathematical proof. These indicate that the required number of colors is not blocked. The examples are not explicit due to the huge number of circles in the example. "While the mathematician Ringel showed that at least 5 colors are needed with the help of an example of 9 circles, in order to show that 5 colors are not enough, one must draw in a certain way 10 to the power of 10,000 circles" explains Prof. Shahar Samrodinsky, from the Department of Mathematics at Ben-Gurion University of the Negev. "It's a much larger number than the number of atoms in the universe. It's amazing that such a large and improbable number is needed to show this."

The answer to the question allows you to save the time of trial and error. "It's simply not possible, don't try to find an algorithm to paint with any given number of colors," Prof. Samrodinsky concluded.

This research (No. 1065/20) was supported by the National Science Foundation.