Trahtman Solution

In late 2007, Israeli mathematician Avraham Trahtman published a proof to the Road Coloring Problem -- a conjecture associated with the field of Graph Theory which asserts that, given a finite number of routes to a destination, a set of directions can be given that will lead to that destination from any given starting point. Many mathematicians had attempted to solve the problem since it was posed in 1970. Trahtman's solution was published in the March 21, 2008 issue of the Israel Journal of Mathematics.

1. Avraham Trahtman: "The solution is not that complicated. It's hard, but it is not that complicated...Some people think they need to be complicated. I think they need to be nice and simple."
2. Joel Friedman, mathematician: "The solution to this problem has definitely generated excitement in the mathematical community."
3. Stuart Margolis, mathematician: "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." Deccan Herald: [Israeli immigrant mathematician solves math riddle (March 21, 2008)

• Avraham Trahtman: the Road Coloring Problem (64KB)
• The Independent: Penniless Migrant Becomes a Maths Superstar (March 21, 2008)
• International Herald Tribune: Israeli Immigrant Mathematician Solves Math Riddle... (March 21, 2008)
  • "In a diagrammatic version of the conjecture – now a theorem thanks to Professor Trakhtman – a 16-line graph forming one square and eight triangles, with the lines coloured red or green, includes two vertices, each representing different destinations. Following the route "blue red red" repeated three times always leads to one, and following "blue, blue red" always leads to the other, whatever the starting point."
• Deccan Herald: Israeli Immigrant Mathematician Solves Math Riddle (March 21, 2008)