Israeli immigrant solves 38-year-old math problem

Tourists who’ve been lost in Japan because they can’t read the street signs know that navigating to new places by street signs alone is reliable only when one can actually read them. Prof. Avraham Trakhtman, an Israeli mathematician from the …

Tourists who’ve been lost in Japan because they can’t read the street signs know that navigating to new places by street signs alone is reliable only when one can actually read them.

Prof. Avraham Trakhtman, an Israeli mathematician from the Department of Mathematics and Computer Science at Bar Ilan University, proposes another solution: it comes by way of a 38-year-old math puzzle known as the “Road Coloring Problem,” which he recently solved.

By throwing some thoughts around on paper, Trakhtman put the nearly four-decade debate to rest. He not only showed that the Road Coloring Problem exists, he also wrote a computer program that explains how to color roads so that it will work in the real world.

And while the math behind the puzzle is complicated, it has implications for the creation of new universal color-coded city maps. And it may even help computers work better too, Trakhtman tells ISRAEL21c.

An example of how the puzzle could be applied is as follows: imagine that your friend comes to your town and doesn’t know where your house is. By giving her a code such as ‘left, right, right, left,’ she could arrive to the destination point (your home) from no matter what point she started.

Trakhtman says that such a code could be useful for police raids, and also for taxi drivers who need to arrive at the same conference hall. A dispatch could give the drivers all the same directions in code, and if followed, the drivers could all arrive to the same point without any further explanation.

Known by his Israeli colleagues as a modest man, Trakhtman’s life is a bit of a Cinderella story. Now 63, and originally from Yekaterinburg, Russia, he came to Israel in 1992 as a new immigrant looking to build a better life.

Although he was an accomplished mathematician in Russia, the first jobs he could find in Israel included maintenance work and a stint as a security guard.

Later, it was at Bar Ilan where Trakhtman was first introduced to the concept of the Road Coloring Problem. Coincidentally, he reports, the problem was first proposed in 1970 by an Israeli team including Prof. Binyamin Weiss from Hebrew University.

Now set for publication in the Israel Journal of Mathematics, his colleagues remark that the solution could have been sent to any prestigious international mathematics journal. But Trakhtman chose to send it to the Israeli journal out of a deep respect for his new country.

Prof. Stuart Margolis, from Bar Ilan’s Department of Mathematics, notes that Trakhtman has already made significant contributions to the world of mathematics. According to Margolis, the last problem solved by Trakhtman has appeared on thousands of websites.