Monday, August 24, 2020

Why Colors Show Up as Icons in Mathematics

 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 R1 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 RR1, 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

[5] http://usatoday30.usatoday.com/tech/science/mathscience/2008-03-20-road-coloring-problem-solved_n.htm

[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

Thursday, June 4, 2020

Color/BW Tropes in Cinema

Once again Carl Jennings has inspired a Hue Angles article from me. This time, Carl’s description of Olafur Eliasson’s black-and-white effect with narrowband light (ISCC News, Issue 489) reminded me of various color/black and white (BW) tropes in cinema. Whereas Tony Stanton’s Munsell 2018 presentation (http://www.iscc-archive.org/Munsell2018_Presentations/Stanton-Breakout-HistoryOfColorCinema.pdf) is a more serious history that highlights the use of color/BW as part of the technological evolution, my essay here highlights some artistic uses of color/BW.

I’ll begin with the Wizard of Oz (1939), wherein the black and white (actually sepia-tone dyed black and white) Kansas shots give way to the dazzling color of Oz. The transition wasn’t trivial: “A set was painted sepia tone and Bobie Koshay, Judy Garland's double was outfitted in a sepia dress and given a sepia make-up job. Koshay walks to the door and opens it, revealing the bursting color of Munchkinland beyond the doorframe. She steps out of the way of the shot and the camera glides through the door, followed by Judy Garland, revealed in her bright blue dress.” [1]

A similar trope occurs in Pleasantville (1998), in which real-life characters are injected into a black-and-white 1950s sitcom. Within the sitcom, the characters (and objects) appear in black and white until they transcend the repression implied by the sitcom and find emotional spontaneity and “modernity” of viewpoint. I find the message is too preachy, but if for nothing else, the film is noteworthy in being claimed to be the first new feature film created by scanning and digitizing recorded film footage to remove or manipulate colors (https://en.wikipedia.org/wiki/Pleasantville_(film) .

Certain resonances of Oz can be seen in Antonioni’s Red Desert (1964), wherein the entire movie has a ghastly blue-green cast (the color, not the actors), until a fantasy scene at the end that opens out to abundant color and lets the audience sigh in relief. That one is not a black-and-white trope, but a reduced-color trope that recalls the Oz transition, but on a more subtle level.

A more powerful recent trope appears in Schindler’s List (1993), which is filmed in black and white except for the Sabbath candles and a red coat worn by a young Jewish girl who is thereby individuated as a casualty of the Holocaust. The emotional effect was a coup by Spielberg. And it used digital techniques for color replacement five years before the vaunted “first” of Pleasantville.

Finally, I must mention the comedic send-up of Psycho’s (1960) shower scene in Mel Brooks’s High Anxiety (1977), which is entirely in color. A bell boy has not-so-pleasant words with a patron in a hotel. The patron (Brooks) wants his newspaper brought to him, and the bell boy waits until the patron is in the shower and then rips the curtain aside and hysterically stabs at him with the rolled-up newspaper. (“There’s your paper!”) The paper falls under the water, and the black ink dissolves—and swirls down the drain in a vortex exactly like the black and white rendered blood that flows down the drain in Psycho. Pan to the patron’s apparently dead face: “That kid gets no tip!” [see https://www.youtube.com/watch?v=__2HBkrrlp4]

There’s no limit to what can be done with the tension between color, and black and white. If you pay attention, you can see BW/color tropes in many other places. My most recent encounter was with the BW world comprising Saul Goodman’s drab alternate identity in Better Call Saul (TV Series). In fact, our editors have experimented with BW/color tension in recent issues of ISCC News.

Michael H. Brill
Datacolor

[1] D. Faraci, True movie magic: how the Wizard of Oz went from black & white to color, written 16 Sep 2013, https://birthmoviesdeath.com/2013/09/16/true-movie-magic-how-the-wizard-of-oz-went-from-black-white-to-color, website accessed 27 Feb 2020.