In the course of researching various martingale-based techniques for profiling network traffic I developed a cute little graph coloring theorem that may well be known, or even trivial using more sophisticated methods. But it was not well known or trivial to me. If it is to you, please contribute references or techniques in a comment to this post.
Although it is not reflected in Equilibrium’s technology (we did monkey around with it for a while before deciding it wasn’t that useful with the sorts of traffic classification schemes and resulting traffic patterns that would typically be encountered in the real world), it was part of our R&D process. But it has applications for devising interesting or useful boundary conditions for various lattice models in physics, such as lattice gauge theory, and it may be useful or interesting to other folks, which is why we’re sharing it.
(The rest of this post is written in a typical mathematical style, so if you do not typically read mathematics it may be tougher sledding than otherwise. Sorry.)
We may associate a graph to the root lattice
by taking and In an abuse of notation, we write It is easy to see that is a perfect graph: i.e., for every induced subgraph there is an independent set of vertices s.t. where is the clique number. Since the chromatic and clique numbers coincide for perfect graphs, we have i.e., is –colorable. Here a -coloring is a map that satisfies for Equivalently, the inverse images are independent.
Producing a periodic -coloring is not completely trivial, however. The difficulty stems from the fact that on one hand cannot be colored with fewer than colors, while on the other hand periodicity requires that some next-nearest-neighbor vertices share colors. It is clear that there is (up to color permutation) a single -coloring of for but it can be shown (i.e., we will show later) that admits more than one periodic 4-coloring.
To begin the construction of a periodic -coloring, let Pick a primitive lattice simplex with as a vertex and extend by coloring the remaining vertices of Different colorings of correspond to overall color permutations. Now the key observation is that for to be periodic while still using only colors, we must have for that
Therefore it is only necessary to consider the coloring on a neighborhood of a vertex.
We do this as follows. First note that the neighbors of are of the form for Introduce an ordering on the neighbors, e.g.
Write for the ordered vertex neighborhood of Now moving from color to color always amounts to acting on by a fixed permutation which we term a coherent color shift. It is not hard to see that in order to induce a coherent coloring the must satisfy
These conditions correspond to the coherence of color shifts on loops of 2 and 3 (or more) steps, respectively. They also ensure that forms a group In the event that produces a periodic -coloring it is called a coherent color shift group.
The equations above are necessary conditions for a coherent color shift. A sufficient condition is that
For if we set and , we have that
for all . In this event is of order and acts freely via color shifts, and therefore has no fixed points, so that no two adjacent vertices are the same color. At the same time, the coloring is periodic because the color shifts depend only on the colors and not the lattice site. If has order less than , the color shift action is not free and there is at least one fixed point, which produces two adjacent vertices of the same color. If on the other hand has order greater than , then the coloring cannot be periodic.
We can put the preceding argument in slightly different language: there exists such that iff , and in this case we cannot have a -coloring. It follows that we must have . Moreover, if for there does not exist some such that , then for generic,
and in this case cannot be periodic. (Here we have used to indicate the action of a coherent color shift.) It follows that a coherent color shift group constructed from some must satisfy , or equivalently that any choice of producing of order when augmented using equations from above yields a periodic -coloring. We refer to this as the minimal periodic coloring theorem.
For the smallest values of we can construct all possible sets and determine whether or not they induce a coherent color shift group along the lines above. The case is trivial. For the only such choices that work are those with and both cyclic permutations, so there is essentially only one 3-coloring of It is left as an exercise for the reader to draw a picture.
For the situation is both more complicated and more interesting, and we’ll cover it (with pictures) in the sequel.
Update: typo corrected, is 3-colorable.