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.

This entry was posted on Monday, August 17th, 2009 at 14:48 and is filed under Equilibrium Networks, Mathematics, Nonrandom bits. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to A minimal periodic coloring theorem, part 1

A minimal periodic coloring theorem, part 2 « Equilibrium Networks says:

21 August 2009 at 03:40

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

Reply

Equilibrium Networks

A minimal periodic coloring theorem, part 1

Like this:

One Response to A minimal periodic coloring theorem, part 1

Leave a Reply Cancel reply

Blogroll

Featured posts

Archives

Categories

Search

Follow “Equilibrium Networks”