Painting the roads

Consider the following problem - given a road system is it possible to have a set of instruction which if followed will cause you to end in one specific point regardless of were you started? Obviously this depends on the road system. It is very easy to give examples of road systems for both cases. It turns out however that there are really simple conditions that guarantee the existence of such an instruction set.
In order to discuss this mathematically we will need to define a few things. Firstly we are not going to talk about roads but about finite directional graphs. Secondly for every vortex on the graph we will allow exactly d (d is the same for all vortexes) edges to come out from it and an unspecified number of edges to go to it. In such situation talking about "turning right" is meaningless so we will instead use colors. Thus every "color" is a function that for a given vortex tells us were to go. Naturally there is d colors. In this blog post I will denote colors with letters - for example (a), (b). Only one color means doing only one "step", so for longer steps we need "words" instead of letters. For example (abdc) means to execute (c) then (d) then (b) and finally (a). In this notation we are looking for a word that when executed will result in us landing on a vortex V regardless of our starting point. We will call such a word a sync word.

Required conditions
Firstly, lets see what obvious conditions are required. Basically we want a graph that is possible to color in such a way that there will be a sync word. So lets demand the following conditions:
1. The graph is strongly connected - there is a path between any two different vortexes.
2. The graph is not cyclic. To be more precise what we want is:
a. The greatest common divisor of the lengths of all the closed paths in the graph is 1.
b. It is not possible to divide the graph to a finite number of sets S1,....Sk such that for all i the edges go from Si to Si+1.

Theorem
The conditions listed above are enough.

Prove history
I am not going to prove this theorem here. It is possible, but it requires a bit too much explanations and the explanations are hard to understand without drawings. Because of this I am not going to prove the theorem, but I will shortly discuss the history behind the prove and some important points behind the proof. If you want to read the actual prove it should be available online (somewhere).

There were three main stages in the attempt to prove the theorem. The first stage was done by Friedman. He defined a weight function of the graph, and showed that if the weigh of the graph is a prime number than there is a way to get a sync word unless the maximum weight (the maximum weight is the weight of the largest (by weight) subset of the graph that can be synced) is 1. As you can see this result is very far from proving the theorem, but it turned out to be an important step - the weight function he defined turned out to be useful in future attempts to prove the theorem.
The second stage was done by Kari. He proved that if the graph also has a fixed number of edges entering each vortex and this number is also d, then there is a way to get the sync word. While this is not what is needed this is a much better result than the previous one. It is also interesting to note that he managed to use induction in his prove, by finding a way to reduce the problem of finding a sync word for a large graph to finding such a word in a smaller graph.
The third and last stage was done by Abraham Tracman. This was done only in 2007. As I already said his prove requires complex explanations so I am not going to say much about it. The only thing that is important to say is that in the prove we look closely on the results of continuously using the same function on the graph. By analyzing the result we find out that in all the cases we can get two vortexes that satisfy a condition needed for Kari proof to work. Basically he showed that it is not needed to ask for a fixed number of edges entering the vortex, and by this completed the proof. In a way this is an interesting example of how people build on other people work.

Conclusion
I hope that by now it is clear that the problem has absolutely nothing to do with roads. Well, except for the name. Originally this problem originated from symbolic dynamics. However the name road coloring sound much better and it is possible to use the result in road building, although it is rather pointless to do so. All we managed to do is to show that there is a way to color the graph, so if we color the roads in the appropriate way we will be able to get the needed instruction set but it will require a more complex road system that what we have now.

In this particular case mathematical analysis of a problem gave a solution that is accurate and possible to use in the real world - but is this always correct? In the next post I will discuss some rather famous cases where correct math leads to solutions that are impossible in the real world.