I don't pretend to begin to understand the question, let alone the answer--but I'm glad it was one of the good guys who solved it!
by Hillel Fendel
(IsraelNN.com) Prof. Avraham Trahtman of Bar Ilan University has solved an internationally famous math problem known as the Road Coloring Conjecture.
From Night Guard to Top Professor
Prof. Trahtman, 63, immigrated to Israel from the former Soviet Union some 15 years ago. He worked at first as a security guard and in house cleaning, and later took his rightful place as a staff member on the Mathematics Faculty at Bar Ilan University in Ramat Gan.
The math problem solved by Prof. Trahtman, a resident of southern Jerusalem, is known as the Road Coloring Conjecture. Its basic format is essentially unintelligible to non-mathematicians, but can be roughly translated into real life by asking: "Is there a map of one-way streets, all colored in one of two colors, for which a set of directions to a certain point can be given that would be correct no matter where one started?"
The problem was originally presented in1970 by Israeli mathematician Binyamin Weiss and two colleagues. It evoked noticeable interest among specialists in graph theory, deterministic automata and symbolic dynamics, though remained unsolved - until Prof. Trahtman proposed his solution this past September. Its publication in The Israeli Journal of Mathematics caused a stir in the mathematical world, and "has brought great pride to our university and the State of Israel," said Bar Ilan President Prof. Moshe Kaveh.
Love of Israel and Modesty
A Bar Ilan colleague of Trahtman, Prof. Stuart Margolis, said, "Not only did he bring about a world breakthrough, but he also chose to publicize it in an Israeli journal, even though he could have publicized it any other international journal. This shows more than anything else his modesty and great love for Israel."
Margolis said that Prof. Trahtman had previously, in his doctorate, "solved problems that mathematicians around the world could not solve."
President Kaveh added that the fact that Prof. Trahtman was a new immigrant "raises once again the need for the government to fulfill its obligation to invest in absorbing immigrant scientists and bringing Israeli scientists back home from abroad."