Archive for April 1st, 2008

Well, first you take a left at the Giant Pineapple…

April 1, 2008

road-coloring.jpgAre you tired of stopping to ask directions? Looking for a way to get from Here to There even if you get lost and aren’t really sure where Here is? Then the Road Coloring Theorem is just the theorem for you!

Intrigued? The Road Coloring Theorem is an algorithm for getting to a specific point on a graph that works no matter where you start. For example, take a look at the graph below:


Suppose this graph represents a series of one-way streets, and you want to get to Yankee Stadium the Yellow Dot. If you start somewhere — anywhere — and follow streets according to the pattern “blue-red-red, blue-red-red, blue-red-red” you’ll arrive there just in time to get a hot dog! Want to go to the Ultimate Elvis Extravaganza Impersonator Contest Green Dot instead? No matter where you are when you start, if you follow “blue-blue-red, blue-blue-red, blue-blue-red” roads, there you’ll be!

But wait, there’s more! According to the Associated Press, this same algorithm could be applied to retrieving lost emails.

How much would you pay paper would you need for such an algorithm? 500 pages, like part of the Four Color Theorem? 150 pages, like Andrew Wiles proof of Fermat’s Last Theorem? The creation of this algorithm required only eight pages of ordinary notebook paper, and one pencil. Oh, and one genius.

Until recently, the idea that any graph could be colored in such a way to allow these universal driving directions was known as the Road Coloring Problem, posed 38 years ago by Benjamin Weiss and Roy Adler. The solution came just last September to Avraham Trahtman, a mathematician at Bar-Ilan University in Israel, and has been making its way recently around the news sites (see for example, The Jerusalem Post on February 8 and The Times yesterday.)