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

by

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:

road-coloring.jpg

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

Tags: , ,

One Response to “Well, first you take a left at the Giant Pineapple…”

  1. Cahit Says:

    There is one similar for the four color theorem.

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

    S T A R G A T E

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: