Cross Products and The Four Color Theorem

1. Overview
2. Coloring edges
3. Gluing two trees
4. Imaginary labels
5. Formation interaction
6. References

Overview

In 1990, the Journal of Combinatorial Theory published a paper by Louis Kauffman that I find very beautiful. It was entitled Map coloring and the vector cross product.

Kauffman’s paper reveals a connection between the algebra of cross products and the famous Four Color Theorem. Since you do not need a mathematics degree to understand the connection, I thought it would be fun to write informally about it.

Figure 1 visualizes the solution to an equation involving a sequence of cross products. Specifically, it represents the equality of two distinct associations of a 6-term cross product, where each term corresponds to one of the circumflex-shaped edges at the top of the figure.

You probably already know that cross products of three-dimensional vectors are not associative. For any three-dimensional vectors A, B, C, the following equation is usually false.

(A x B) x C = A x (B x C)

Of course, there are uninteresting values of A, B, C for which the above equation is true. For example it is true when all three vectors are zero-length, or when all three vectors are equal.

It is more interesting to ask for a solution such that both sides are non-zero, and such that the unknown terms are restricted to the three basis vectors of ℝ³. Given these constraints, the equation still has a solution. For example, I, K, and I can be assigned to A, B, and C, respectively. This works:

(I X K) X I = I X (K X I)

Let’s call this an “interesting” solution. The left and right sides of this equation are associations for a product of n vectors.

We have shown that an interesting solution exists when n = 3, but do interesting solutions exist when n > 3?

Yes, interesting solutions do exist! In fact, they always exist, for any number of terms and any placement of parentheses. We know this is true because we know that the Four Color Theorem is true.

More formally, Kauffman showed that the following two statements are equivalent. (In a proper coloring of items, no two adjacent items have the same color.)

• Kauffman’s Cross Product Theorem. If L and R are associations of the n-term cross product AxBxCx…, then there exists a nonzero solution to the equation L = R for any n, and for any choices of L and R.
• The Four Color Theorem. (4CT) The faces of any trivalent bridgeless plane graph can be properly colored using 4 or fewer colors.

The way that I’ve expressed the 4CT above might seem more constrained than the classic definition, but it can be shown that it is an equivalent statement.

Coloring edges

Kauffman leverages a well-known reformulation of the 4CT discovered by Peter Tait in the late 1800’s, described as follows.

• Tait’s Edge Color Theorem. (3EC) The edges of any trivalent bridgeless graph can be properly colored using 3 or fewer colors.

To go a little deeper, you can see my previous post but let me summarize here. Suppose you already have a proper 4-coloring of the faces in a trivalent graph, as on the left in the following figure. Next, assign a 2-digit binary number to each color. Since no two adjacent faces have the same color, applying an XOR operation to any two adjacent faces would never result in 00. Therefore, an edge coloring produced by XOR’ing adjacent faces is a 3-coloring, as shown on the right.

Next let’s show that this 3-coloring is actually a proper 3-coloring, meaning that no two edges emanating from a single vertex have the same color. All vertices are trivalent, so there are only two configurations of surrounding colors when ignoring rotation, as shown below. In this diagram, I intentionally swapped green with purple. Later in the post you’ll see why I did this, and why I labeled each of the configurations with a complex number.

Given that no two adjacent faces can have the same color, it is obvious that no two sister edges can have the same color. Therefore we’ve shown that 4CT implies the 3EC.

To show that the 3EC implies the 4CT, we need to construct a proper face coloring from a proper edge coloring. This involves the process of creating formations. Formations are cycles that arise from a proper edge coloring after removing one of the colors.

Two formations are shown below. The left formation was produced by removing red edges from the 3-coloring, and the right formation was produced by removing green edges.

Note that removing one color always results a graph where the degree of every vertex is 2. It is well known that every even graph (i.e. a graph whose vertices all have an even-numbered degree) can be decomposed into cycles.

After creating formations from an edge coloring, a proper face coloring can be obtained by overlaying the formations on top of each other, then assigning a color to each region based on the set of enclosing formations. See my previous post for details.

Gluing two trees

A binary tree with n leaves can be used to represent an association of an n-term cross product. Two associations are depicted below.

Since the respective terms of the two associations are equal, we can glue together the leaves of the two graphs. The two root nodes can be combined as well, since we wish to find a solution for which the LHS is equal to the RHS.

Note that we flipped the right-hand tree around the Y axis to remove crossings. We have also given the graph a proper 3-edge coloring, which we know is always possible, because this is a trivalent bridgeless graph.

Imaginary labels

Let’s assign I, J, and K to each of the edge colors in Figure 8, then split the graph back into two binary trees. This provides us with a solution of sorts, except that sign is indeterminate. (Recall that cross products are not commutative.) See the following figure, where we assigned I to green, J to red, and K to blue.

Refer to Figure 4 to see how we labeled each vertex with complex numbers i and  − i. We can see now that taking the product of all the complex vertex labels in the left tree results in the correct sign for its corresponding cross product. Note that the tree on the right is a mirror image of the original cross product, so we will need to flip the sign of all its labels.

This begs the question: is the product of vertex labels from the left tree always equal to the negated product from the right tree? If we can prove this, then we’ll prove that the 4CT implies Kauffman’s cross product theorem.

Formation interaction

To prove that the complex product in the LHS is always equal to the complex product in the RHS, we will first show that the complex product for the merged graph is equal to +1. This was first described by Roger Penrose in 1971, but Kauffman provides a visual proof as follows.

First, take the formations that we produced by removing a certain color from the edge coloring. Below we show the formations produced by removing green edges (left) and red edges (middle). The figure on the right shows the overlay of these formations. This device can be used to produce a proper 4-coloring of faces, but here we will use it to show that the complex product must always be 1.

Formation vertices always have degree 2, so we know from graph theory that they consist of a disjoint set of cycles. Since the red and blue formations are embedded in the same trivalent graph, they can interact in only one of the following two ways.

1. The blue cycle shares an edge with the red cycle and has either a separate interior, or a wholly-contained interior. This is a bounce, depicted on the left below.
2. Or, the interiors of the red and blue cycles partially intersect. This is a cross, shown on the right below.

Since these are the only ways in which cycles can interact when they are embedded in the same trivalent graph, we can examine their vertex configurations to make observations about the product of complex labels:

1. Each bounce consists of a  + i vertex and a  − i vertex, and therefore contributes  + 1 to the product.
2. Each cross consists of two edges: a pair of  + i vertices and a pair of  − i vertices. Each cross therefore contributes  + 1 to the product.

Since each bounce (one edge) and each cross (two edges) contributes 1 to the product, the product of complex labels over the glued graph must always be 1.

Next we need to show that the sign of the label product in the left tree (L) is equal to the sign of the label product in the right tree (R). Recall that we flipped the right tree along the Y axis in order to obtain a planar graph. Therefore we now know that the following is true:

L * Mirror(R) = 1

In L, we can say that there are a verts labelled with i and b verts labelled with  − i. In R, let’s say that there are c verts with i and d verts with  − i. Moreover, from Figure 4 we know that a mirror operation is equivalent to negating each complex label. Thus:

i^a( − i)^b * ( − i)^ci^d = 1

As a final step, multiply each side by i^c( − i)^d and simplify:

i^a( − i)^b = i^c( − i)^d

Thus:

L = R

Et voilà!

Philip Rideout, 31 May 2020.

References

Kauffman, L. H. (1990). Map coloring and the vector cross product. Journal of Combinatorial Theory, Series B, 48(2), 145-154.

Penrose, R. (1971). Applications of negative dimensional tensors. Combinatorial mathematics and its applications, 1, 221-244.

Whitney, H. (1931). A theorem on graphs. Annals of Mathematics, 378-390.