The nearly 4-decade old "road colouring problem" has been
solved* by an Israeli mathematician Avraham Trahtman. Although the news
item has appeared only this month, the solution of the problem appeared
in Israel Journal of Mathematics, 21 December 2007. Trahtman's paper
is available at



http://arxiv.org/pdf/0709.0099v4 <http://arxiv.org/pdf/0709.0099v4>





Comments on this problem are welcome as it has important implications
for computer science, for example, in ensuring that an email reaches the
specified destination no matter from where it originated.



Dr D.C.Misra

March 22, 2008

______________________________________________________________________

*Israeli mathematician cracks 38-year-old math riddle

Associated Press

Posted online: Saturday, March 22, 2008 at 0018 hrs



JERUSALEM, MARCH 21 : A mathematical mystery that has baffled the top
minds in the esoteric field of symbolic dynamics for nearly four decades
has recently been cracked — by a 63-year-old former security guard.

Avraham Trakhtman, a mathematician who worked as a labourer after
immigrating to Israel from Russia, has succeeded where dozens failed,
solving the elusive Road Colouring Problem.

The conjecture essentially assumes that it is possible to create a
"universal map" that would direct people to arrive at a certain
destination, at the same time, regardless of their original location.
Experts say this proposition, which seems to defy logic, could actually
have real-life applications in the fields of mapping and computer
science.

"In math circles, we talk about beautiful results — this is
beautiful and it is unexpected. Even in layman's terms it is
completely counterintuitive, but somehow it works," said Stuart
Margolis, a colleague who recruited Trakhtman to Bar Ilan University
near Tel Aviv.

He said the discovery was especially remarkable given Trakhtman's
age and background. "The first time I met him he was wearing a night
watchman's uniform," he said.

The Road Colouring Problem was first posed in 1970 by Benjamin Weiss, an
Israeli-American mathematician, and a colleague, Roy Adler, who worked
at IBM at the time.

Weiss said he believed that given a finite number of roads, one should
be able to draw up a map, coded in various colours, that would lead to a
certain destination regardless of the point of origin.

For eight years, he tried to prove his theory. Over the next 30 years,
some 100 other scientists attempted to as well. All failed, until
Trakhtman came along and, in eight short pages, jotted the solution down
in pencil last year.

Trakhtman said it took him a year to solve the problem. But that
wasn't nearly as impressive as the journey he took to get to his
current lofty position.

Originally from Yekaterinburg, Russia, Trakhtman was already an
accomplished mathematician before he came to Israel in 1992, at the age
of 48. But like many immigrants in the wave that followed the breakup of
the former Soviet Union, he too struggled to find work in the Jewish
state and was forced into stints working maintenance and security before
landing a teaching position at Bar Ilan in 1995.

The soft-spoken Trakhtman declined to discuss his arduous odyssey,
saying those were the "old days." He said he was "lucky"
to be recognized, but played down his recent achievement as a
"matter for mathematicians" and said it hasn't changed him a
bit.

"The solution is not that complicated. It's hard, but it is not
that complicated," he said in heavily accented Hebrew. "Some
people think they need to be complicated. I think they need to be
simple."

Trakhtman's solution will soon be published in the Israel Journal of
Mathematics.

Joel Friedman, a math professor at the University of British Columbia,
said probably everyone in the field of symbolic dynamics has tried to
solve the Roadmap Coloring Problem at some point, including himself. He
said people in the related disciplines of graph theory, discrete math
and theoretical computer science have also tried.

"The solution to this problem has definitely generated
excitement," he said in an e- mail message. Trakhtman's
achievement is hardly the longest open problem to be solved recently. In
1994, British mathematician Andrew Wiles solved Fermat's last
theorem, which had been open for more than 300 years. Margolis,
Trakhtman's colleague at Bar Ilan, said the solution could have many
applications.

"Say you've lost an e-mail and you want to get it back — it
would be guaranteed," he said. "Let's say you are lost in a
town you have never been in before and you have to get to a friend's
house and there are no street signs — the directions will work no
matter what."

(Source: The Indian Express, New Delhi, Saturday, March 22, 2008, p-16
http://www.indianexpress.com/story/287398.html



[Non-text portions of this message have been removed]