The road coloring conjecture was proved recently after almost four decades by an Israeli mathematician. The theorem states that given a finite number of roads, it is possible to draw a universal color-coded map that leads to a particular destination regardless of the point of origin. This is equivalent to saying there is a set of synchronized instructions from any point within a network to a certain other point that would work regardless of which node you start from.

“For example, consider the vertex marked in yellow. No matter where in the graph you start, if you traverse all nine edges in the walk “blue-red-red—blue-red-red—blue-red-red”, you will end up at the yellow vertex. Similarly, if you traverse all nine edges in the walk “blue-blue-red—blue-blue-red—blue-blue-red”, you will always end up at the vertex marked in green, no matter where you started.”

This problem has many real world implications, from message and traffic routing to search algorithms to finding directions. In the cases of graph networks or the trading graph networks discussed in class, it shows that is is always possible to find or track a route to a certain node from any other node. So the flow of information within a network can always be traced from a set of synchronized instructions for every node. Lost emails can always be tracked down and directions to a friends house are available from a single set of instructions from anywhere in the network. With regards to searching algorithms and online advertising, this process could be manipulated to direct traffic towards a particular site.

Referenced articles:

http://en.wikipedia.org/wiki/Road_coloring_problem

http://ap.google.com/article/ALeqM5g2lh1_jNDbrmhNoMlwkZTfLeCw8gD8VHBPIO0

http://arxiv.org/pdf/0709.0099v4