In eerie resonance with Euclid’s definition of a point as “that which has no part,” J. Lettvin’s Colors of Colored Things begins with the following: “Judgment of color (including brightness) seems not to depend on extension [… Redness] is like nothing else but itself, it cannot be decomposed or described, but only exhibited; it is a simple.” [1] Lettvin goes on to discuss (in his unique way) the familiar complications of how vision transforms stimuli into color, but he retains the view that the judgment of color is a simple. I will now look at some implications of this idea.
Color as a simple is readily added to a geometrical object, and the color icons enrich the meaning. Examples range from traffic signals to the stylized footprints in an Arthur Murray dance studio. But mathematics offers some particularly interesting morsels. Three come to mind. One of these, the four-color map problem has been described in an earlier Hue Angles [2]. Another shows up in the title of Arthur Loeb’s book Color and Symmetry [3], in which permutations of color coding in a pattern enrich the geometric symmetries incurred by such operations as glides and reflections. Now I want to introduce you to a third, perhaps less familiar example, the road-coloring problem.
The road-coloring problem involves a network with directed paths between pairs of vertices. Under some surprisingly general conditions, it is possible to color-code the paths so that, given a destination vertex, a single set of instructions in the form of a sequence of color choices will bring you from any source vertex to the same destination vertex. The Wikipedia article on the road-coloring problem sets the context: “In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from.” You start with a graph with numbered vertices and colored arrows between the vertices. The arrows are like one-way streets: the instructions (a sequence of path colors) assume you are always going in the direction of the arrow you’re on. To convince yourself that this behavior is possible, try the exercise based on the eight-vertex graph in Ref. [4].
The road-coloring problem started as a conjecture by Benjamin Weiss in 1970, but it took 38 years to prove. The proof came from Avraham Trahtman, a 63-year-old Israeli former security guard (who was a mathematician in his earlier life in the USSR) [5]. Trahtman [6] proved not only that the nominated graphs all had coloring sequences with the desired property, but also that one’s mathematical life can peak long after one’s teens and twenties.
Encouraged by checking the eight-vertex graph in Ref. 4, I wondered if I could make a simpler graph with only three nodes that had the same property. In the figures I show here, three nodes support two possible solutions, but I had to allow the possibility of paths from a node to itself.
Drawing of two three-vertex road-coloring solutions (author, 2013). The medium is felt marker on flip-chart paper, photographed in a cool-white-fluorescent-lit office. Not surprisingly, the “red” looks very orange. My apologies, but I hope the idea is clear.
In the case of my first graph, if you live at vertex 1, all you have to tell your visitor is “take the red arrow from where you are to the next vertex (in the direction indicated by the arrow), and that will be node 1. That’s what I mean by the instruction R→1 from anywhere (i.e., from vertex 1, 2, or 3). Similarly, if you live at vertex 2, your instruction is “take the green path one step from wherever you are.” If you live at vertex 3, your instruction is “take the blue path.” Because the arrows are like one-way streets, you must always go in the direction of the arrow you choose.
In the second graph, there are still only three vertices, but the paths involve two steps and not just 1. Starting from vertex 1, 2, or 3, if you take two R steps, you end up at vertex 1. I denote that action as RR→1, etc. But notice that I use only two colors of path instead of three (as in my first graph). There is a tradeoff between the number of colors and the length of the instruction string.
What use is the road-coloring problem (now a theorem)? It serves very well in the theory of automata. To quote Weifu Wang [7], “When the automaton is running and encounters an error, and if the road coloring conjecture is true, the automaton can always follow a certain sequence and go back to the previous correct state, regardless of what error it encountered.” I think the “correct state” is the address of the person giving the instructions, and the “error state” is where the presumed visitor is when he gets instructions. It’s a little confusing to call the direction “back” when you’re proceeding forward along the arrows to get there. But synchronizing a move to an earlier known state seems the key to the application.
One place not to use the road-coloring theorem is in an Arthur Murray dance studio. Imagine giving a color-sequence instruction set to a bunch of dancers and have them all pile on top of each other when they (synchronously) reach the home vertex.
[1] J. Y. Lettvin, MIT RLE QPR 87, 1967, p. 193, dspace.mit.edu/bitstream/handle/1721.1/55670/RLE _QPR_087_XIV.pdf
[2] M. H. Brill, http://hueangles.blogspot.com/2013/03/
[3] A. Loeb, Color and Symmetry, Wiley, 1971.
[4] https://en.wikipedia.org/wiki/Road_coloring_theorem
[6] A. N. Trahtman, The Road Coloring Problem. Israel Journal of Mathematics, Vol. 172, 51–60, 2009
[7] W. Wang, The Road Coloring Problem. (2011). https://math.dartmouth.edu/~pw/M100W11/weifu.pdf
.
Michael H. Brill
Datacolor
