You are here

Four-Decade-Old "Road Coloring Conjecture" Apparently Solved

February 25, 2008

Avraham Trakhtman (Bar-Ilan University, Ramat Gan, Israel) has apparently solved the "Road Coloring Conjecture," which was raised by, among others, Israeli mathematician Binyamin Weiss in 1970. The solution is slated to appear in the Israel Journal of Mathematics within the next few months.

Trakhtman, 63, who had worked as a guard for five years after emigrating to Israel from the Soviet Union in 1990, has generated excitement among mathematicians in his mathematical specialty: semigroup theory, which is a branch of algebra and the algebraic way of examining computer science.

The “Road Coloring Conjecture” deals with synchronized instructions. The problem is whether by using such instructions, one can reach or locate an object or destination when lost within a city, maze, or network, etc.

Colleague Stuart Margolis pointed out that Trakhtman's work "proves that it's always possible to find one's way with such instructions." Trakhtman is writing an algorithm to implement his solution.

There are many seemingly insoluble math problems like the “Road Coloring Conjecture.” "We are paid to solve them," said Margolis.

Source: The Jerusalem Post

Start Date: 
Monday, February 25, 2008