Abstract math problem that has befuddled experts for the last 38 years.
By JUDY SIEGEL-ITZKOVICHAvraham Trakhtman 88(photo credit: )
A 63-year-old mathematics professor at Bar-Ilan University, who worked as a guard for about five years after his aliya from the former Soviet Union in 1990, has solved an abstract math problem that has befuddled experts for the last 38 years.
Prof. Avraham Trakhtman finally found the solution, which will be published in a few months in the Israel Journal of Mathematics, solely by tossing it around in his brain and using a pencil and paper. His research, which has already been placed on a Web site for professionals and is available for download, has elicited much excitement among mathematicians in the esoteric field.
Trakhtman solved the "Road Coloring Problem," which was raised by Israeli mathematics Prof. Binyamin Weiss and others in 1970. There are many forms but the most popular one among experts goes like this:
A man reaches a town he has never visited before and drives around trying to find the home of his friend even though there are no street names. The friend says not to worry and that he will provide instructions (left, right, left...) on how to get there.
This is called synchronizing instruction. The problem is whether by using such instructions, the driver could reach his destination no matter where he was lost, said Prof. Stuart Margolis, a colleague and mentor of Trakhtman who made aliya from the US and joined Bar-Ilan the same year as the Russian mathematician.
"He is brilliant with a high IQ," Margolis told The Jerusalem Post. "It's God-given gray matter in his brain. He is shy, reserved and very modest. He intentionally offered his paper to an Israeli journal even though any mathematics journal in the world would be overjoyed to get it. Now he's working on a real algorithm to implement his solution."
There is also a computer version of the problem: One has a big network like the Internet, and an e-mail message is lost somewhere. The systems operator wants to get it sent to the right place, said Margolis. "But he doesn't know where it is. Synchronizing instructions could get it there, like a mouse through a maze. Avraham's work proves that it's always possible to find one's way with such instructions."
Trakhtman's colleagues, who were following his instructions, could quickly see that his solution was correct as he prepared proofs with paper and pencil. Nevertheless, it still must go through the referee process.
Trakhtman was in his mid-40s when he came on aliya from Sverdlovsk (now Yekaterinburg) in the Ural Mountains. "He received his degree at the University of the Urals, but he had trouble working as an academic because he made it clear that he was Jewish," Margolis said.
Trakhtman has a second wife and a young child here and an older child in the former Soviet Union. His mathematical field is the same as Margolis's - semi-group theory, which is a part of algebra and the algebraic way of examining computer science.
"When he applied for work at Bar-Ilan, a colleague of mine noticed that Avraham was in the same field as mine. I had heard of him before, as he had written very important papers. When he applied for a job in the mathematics department, he was hired to teach and do research," Margolis said.
There are many other seemingly insoluble math problems like the "Street Coloring Problem," said Margolis. "We are paid to solve them."
