Are 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.)

### Like this:

Like Loading...

*Related*

Tags: direction, road coloring, Trahtman

This entry was posted on April 1, 2008 at 8:34 pm and is filed under Math in the News. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

April 4, 2008 at 7:14 am |

There is one similar for the four color theorem.

See http://arxiv.org/abs/math/0408247 or http://arxiv.org/abs/0710.2066