A minimal periodic coloring theorem, part 1

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 (V,E) to the root lattice

A_{n-1} := \{ x \in \mathbb{Z}^n : x_1 + \cdots + x_n = 0\}

by taking V \equiv A_{n-1} and (x,y) \in E \iff \lVert x - y \rVert= \sqrt{2}. In an abuse of notation, we write A_{n-1} \equiv (V,E). It is easy to see that A_{n-1} is a perfect graph: i.e., for every induced subgraph G \subset (V,E) there is an independent set of vertices H s.t. \omega(G - H) < \omega(G), where \omega(\cdot) is the clique number. Since the chromatic and clique numbers coincide for perfect graphs, we have \chi(A_{n-1}) = n: i.e., A_{n-1} is n-colorable. Here a k-coloring \kappa : V \rightarrow \{1,\dots,k\} is a map that satisfies \kappa(x) \ne \kappa(y) for (x,y) \in E. Equivalently, the inverse images \kappa^{-1}(j) are independent.

Producing a periodic n-coloring is not completely trivial, however. The difficulty stems from the fact that on one hand A_{n-1} cannot be colored with fewer than n 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 n-coloring of A_{n-1} for n=2,3, but it can be shown (i.e., we will show later) that A_3 admits more than one periodic 4-coloring.

To begin the construction of a periodic n-coloring, let \kappa(0) = 1. Pick a primitive lattice simplex \Delta with 0 as a vertex and extend \kappa by coloring the remaining n-1 vertices of \Delta. Different colorings of \Delta correspond to overall color permutations. Now the key observation is that for \kappa to be periodic while still using only n colors, we must have for (x,y) \in E that

\kappa(x) = \kappa(x+z) \iff \kappa(y) = \kappa(y+z).

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 x \in A_{n-1} are of the form x - e_j + e_k for j \ne k. Introduce an ordering \prec on the neighbors, e.g.

x - e_j + e_k \prec x - e_\ell + e_m \iff (j < \ell) \lor (j = \ell \ \land \ k < m).

Write \nu(x) for the ordered vertex neighborhood of x. Now moving from color \kappa(x) to color \kappa(y) always amounts to acting on \kappa(\nu(x)) by a fixed permutation \sigma_{\kappa(x)\kappa(y)} \in S_n, which we term a coherent color shift. It is not hard to see that in order to induce a coherent coloring the \sigma_{jk} must satisfy

\sigma_{kj} = \sigma_{jk}^{-1}; \quad \sigma_{jk}\sigma_{k\ell} = \sigma_{j\ell}.

These conditions correspond to the coherence of color shifts on loops of 2 and 3 (or more) steps, respectively. They also ensure that e \cup \{\sigma_{jk}\}_{j \ne k} forms a group \Gamma_\sigma. In the event that \Gamma_\sigma produces a periodic n-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

\{\sigma_{jk}\}_{j \ne k} = \{\sigma_{1k}\}_{k=2}^n.

For if we set \sigma_{k1} := \sigma_{1k}^{-1} and \sigma_{jk} := \sigma_{j1} \sigma_{1k}, we have that

\sigma_{jk} \sigma_{k\ell} = \sigma_{j1} \sigma_{1k} \sigma_{k1} \sigma_{1\ell} = \sigma_{j1} \sigma_{1\ell} = \sigma_{j\ell}

for all k. In this event \Gamma_\sigma is of order n 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 \Gamma_\sigma has order less than n, 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 \Gamma_\sigma has order greater than n, then the coloring cannot be periodic.

We can put the preceding argument in slightly different language: there exists j \ne k such that \sigma_{1j} = \sigma_{1k} iff \sigma_{jk} = e, and in this case we cannot have a n-coloring. It follows that we must have \lvert \Gamma_\sigma \rvert \ge n. Moreover, if for j \ne k there does not exist some \ell such that \sigma_{jk} = \sigma_{1\ell}, then for x generic,

\sigma_{jk} \cdot \kappa(x) \notin \{\sigma_{1\ell} \cdot \kappa(x)\} = \{1,\dots,n\} \backslash \kappa(x),

and in this case \kappa cannot be periodic. (Here we have used \cdot to indicate the action of a coherent color shift.) It follows that a coherent color shift group constructed from some \{\sigma_{1k}\}_{k=2}^n must satisfy \lvert \Gamma_\sigma \rvert = n, or equivalently that any choice of \{\sigma_{1k}\}_{k=2}^n producing \Gamma_\sigma of order n when augmented using equations from above yields a periodic n-coloring. We refer to this as the A_{n-1} minimal periodic coloring theorem.

For the smallest values of n we can construct all possible sets \{\sigma_{1k}\}_{k=2}^n and determine whether or not they induce a coherent color shift group along the lines above. The case n=2 is trivial. For n = 3, the only such choices that work are those with \sigma_{12} and \sigma_{13} both cyclic permutations, so there is essentially only one 3-coloring of A_2. It is left as an exercise for the reader to draw a picture.

For n=4 the situation is both more complicated and more interesting, and we’ll cover it (with pictures) in the sequel.

Update: typo corrected, A_2 is 3-colorable.

One Response to A minimal periodic coloring theorem, part 1

  1. [...] minimal periodic coloring theorem, part 2 As mentioned previously, for the situation regarding minimal periodic colorings of is more complicated. The [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

%d bloggers like this: