5.  The Coloring Equations

Now let’s see how the automatic coloring scheme is carried out. We begin by considering the following display of Escher’s motif, with the index of each of the five pieces displayed at the outer edges (rim) of the unit square, thus illustrating the internal package function AddLabels. For this and other internal functions to work, we must enter the innermost context of the Escher package.

Figure 20.  Escher’s motif with labels identifying the pieces.

Now, given a signature (we use throughout this section), we place transformed versions of the labeled motif into a tile. We color each polygonal piece differently for now. The idea is to set the colors of adjoining polygons equal. In fact, we will let Mathematica do just that for us, by associating a variable with the color of each Polygon in our tiling, writing the appropriate equations to reflect these equalities, and using Solve. First, we associate the variable names x, y, z, w with the cells in a tile, as shown in Figure 21.

Figure 21. Placing the motifs into a tile according to a signature shows the color-matchings that are required.

Now we index the variables x, y, z, w according to the individual polygons in each cell. Where polygons connect, their colors must be equal. This generates equations such as the following.

But this is not sufficient, for this tile does not exist in isolation, but is part of, well, a tiling! And that means it is surrounded by other tiles, so more colors must match. Now if we were to require that each tile be identically colored, we could add a few more equations to indicate that. The colors on the right in cells y and w would match those on the left in cells x and z, and similarly, the tops of x and y must match the bottoms of z and w. (This is the case when the big tile size is .) Thus we would also require the following.

However, things are not that simple for a larger big tile size, in which we require the colors to match only after a certain number of repetitions, horizontally and vertically. So to accommodate that, we will index each variable by its location in a big tile.

Figure 22. This shows how one can use the signature and the big tile size (4×2 in this case) to come up with a system of very simple equations whose solution yields a proper coloring of the final pattern.

So now we end up with a new (and substantially larger!) set of equations. The requirement of periodicity can be seen in the equations at the end of the following list.

Let’s solve the 48 equations with Solve (for the 10×10 big tile example in Figure 18, the system sent to Solve has 600 equations and 500 variables!!). The system is clearly a singular homogeneous linear system and as such has nontrivial solutions that can be expressed in terms of a number of free variables. These are just what we want, for we may assign a unique color to each free variable and obtain a correctly colored system. (By that we mean that all connected polygons have the same color. Later we will consider correct colorings having a minimum number of distinct colors.) Note that Solve returns a solution expressed in terms of a maximal set of free variables equal in number to the nullity of the system.

While it might seem more natural to use LinearSolve to solve the system. the solution returned by that command is not a general solution. The one returned by Solve is general. Also, our system is sparse (meaning that the matrix representing the system contains a high proportion of zero entries) and Solve uses special algorithms for speeding the solution of sparse systems. On the other hand, not only is our system sparse, but all of the equations are of such a simple form (x==y) that it would be of interest, and possibly beneficial, to obtain a general solution instead by a clever application of  Replace. We leave that problem to the intrepid reader.

Returning to our coloring problem, the next step is to turn the free variables into a set of color indices. We omit most of these details. In this example it can be seen that there are 8 free variables: . Some easy coding transforms them into a set of color instructions. In fact, AutoColorAlgorithm returns precisely that set of color instructions.

Placing these into our display, and straining our eyes a bit, we see the colors all match. We are also perhaps straining the reader’s patience by revealing at this time another capability of our weaving code! The letter “a” is used by Escher and by us to reverse the order of polygons (to enhance the weaving), but our package also accepts other functions. The example that follows show how to use RotateLeft and RotateRight to affect the weaving order. Examine the motif copies carefully and you will see that the order of polygons is different than before; the virtue of this will become clear in Figure 25. And we have labeled the polygons in the tiling with the polygon numbers followed by the color numbers, for ease of comparison to the preceding array.

Figure 23. The labels in this image have the form (polygon index):(color number). A close look shows that colors of abutting polygons all match.

EXERCISE.  An exceptionally observant reader might observe an interesting relation among the colors of horizontally (or vertically) adjacent tiles that we compute: they are fixed permutations of one another. Why?

We deserve to see this one without the labels after all that work! The ShowNumberOfColors option gets us a printed reminder that the number of colors used is equal to the number of free variables. We return here to the plain signature.

Figure 24.  The result of the automatic coloring algorithm is a pattern where distinct strands that cross get distinct colors. Eight colors are used in this example.

We now repeat the preceding command, invoking our minimal-coloring algorithm (which is the default setting in the package, but was overridden in the preceding call by the explicit color instructions), as we turn finally to the problem of how to determine the minimum number of colors necessary to properly color the tiling. We seek the placement of as few colors as possible so that the strands are not merely single colors, but also so that if two distinct strands cross, then they have different colors. We return to the fancy weaving using rl and rr in the signature.

Figure 25. When the MinimumColoring option is used, the automated routines produce a pattern that uses only two colors. And here we use a fancy weaving to make the pattern pass through the small diamonds!

Look at the labeled pieces of EscherMotif again (Figure 20) and notice that polygons #1 and #4 cross, as do #4 and #5. A routine in the package detects this.

Now we already have a set of colors for the polygons, from AutoColorAlgorithm, and this is essentially a maximal coloring in that each separate strand in a big tile has its own color. Now we want to know which pairs of these colors correspond to strands that cross. To understand the following output, refer to the previous output and Figure 23.

Now we can get a unique list of unordered pairs of crossing colors.

So this is the complete set of pairs of colors that must be different. A convenient device for visualizing this situation is a graph, which is a set of vertices (in this case the distinct colors in aca) and edges, which are the unordered pairs of adjacent vertices. Compare the adjacent colors in the graph represented below with the crossed colors of the maximally colored tiling in Figures 23 and 24 above. Also notice that the colors that do not get crossed at all correspond to isolated vertices in the graph.

Figure 26. The graph representing the crossed colors of the tilings in Figures 23 and 24 has 8 vertices corresponding to the 8 colors of the tiling. Colors that cross in the tiling correspond to vertices joined by edges in the graph.

The assignment of unique numbers (colors) to the vertices of a graph so that adjacent vertices always have different numbers is called a coloring or proper coloring of the graph. Of course, that terminology has nothing to do with the colors we have been discussing, but in fact the graph above is already properly colored, albeit in a trivial way, with a maximum number of colors. We want a minimal coloring of our tiling, and that will be easy when we have a minimal coloring of our 8-vertex graph. The graph in Figure 27 illustrates such a minimal coloring, requiring only 2 colors. The minimum number of colors required to color a graph is called the chromatic number of the graph. (Some of our examples are more complicated, such as a 30-vertex graph with chromatic number 5 for the example of Figure 18). In Mathematica’s standard  package DiscreteMath`Combinatorica` is the function VertexColoring, which takes a graph and returns a minimal set of colors for its vertices. (Note the following disclaimer, quoted from that package: “VertexColoring[g] uses Brelaz’s heuristic to find a good, but not necessarily minimal, vertex coloring of graph g.”)  Having just invoked the coloring routines to get Figure 25, we can examine some of the internal data, such as vcol (recall that in this section we are working in the package’s internal context), and see how the graph gets minimally colored. The list vcol is returned by VertexColoring.

Figure 27. The graph in Figure 26 can be 2-colored. The color replacements are shown here as labels.

Applying the replacements to our list of colors gives us new color instructions, which are the same as were computed automatically for Figure 25. The output of the following is in essence identical to Figure 25, but illustrates the ColorsUsed setting to PolygonLabels to show exactly how the colors are used.

Figure 28.  The package includes functions that can generate labeled diagrams that show exactly how the colors are used. This image shows how the two colors in this example match up along the edges.