Wednesday, March 26, 2008
Wednesday Math, Vol. 18: The Road Coloring Problem
So here's the deal. You have a closed system of locations and one way-streets leading from location to location. If you pick any two locations, there exists a series of roads leading from one place to the other and vice versa. For every location, there are the same number of roads leading out, and that number is at least two. There's also a rule about the length of round trips, that they can't all be divided by some number bigger than one. This would make the synchronization we seek impossible.
Since every location in the picture above has two roads leading out, and since I am a good leftist and all, I paint the choices red and black. It's the painting choice that matters, because not all of the possible painting choices will allow me to do the thing I can do with this choice. Pretend there is an army of robots (or in math, automata) wandering around this system of locations, known in math as a graph. I can broadcast messages to all of them simultaneously, telling them what color road to take next. If they are spread all over the place, I can send the message black, black, black, red, and no matter where they started, all of them will be at location B when they finish those four moves. Since one of the rules is that there is a path from any location to any other, that means I can send a broadcast that will get all the robots to any location simultaneously, once I have them all in lockstep at location B.
The unsolved problem was if there was a coloring that would have this synchronization process for any graph that met all the stipulations, no matter how big, no matter how many roads leading out all the locations had. The answer is yes, according to a paper published in 2007 by Avraham Trahtman, a Russian mathematician now living in Israel. The problem was first proposed in 1970, by mathematicians other than the solver, and some are making a fuss over the fact that Trahtman is 63 years old, when math is supposed to be a young person's game. In point of fact, though a lot of important math is done by people under the age of 30, there are plenty of instances of people still doing good work all their lives, or having the big breakthrough well past the age of 30.
Kudos, Dr. Trahtman!