A minimal periodic coloring theorem, part 2

As mentioned previously, for $n=4$ the situation regarding minimal periodic colorings of $A_{n-1}$ is more complicated. The assignment

$\sigma_{12} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{smallmatrix} \right), \quad \sigma_{13} \equiv \left( \begin{smallmatrix}1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{smallmatrix} \right), \quad \sigma_{14} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \end{smallmatrix} \right)$

works and produces the essentially unique periodic cyclic coloring of $A_3.$ This name reflects the fact that the induced $\Gamma_\sigma$ is isomorphic to the cyclic group $\mathbb{Z}_4.$

The cyclic coloring of <img src='http://s0.wp.com/latex.php?latex=A_3&bg=ffffff&fg=333333&s=0' alt='A_3' title='A_3' class='latex' />. For comparison with a later figure, take 0 to be the vertex at the top of this figure.” width=”300″ height=”274″ /><p class=

The cyclic coloring of $A_3$ . For comparison with a later figure, take 0 to be the vertex at the top of this figure.

There are also essentially three inequivalent periodic 4-colorings with $\Gamma_\sigma \cong \mathbb{Z}_2^2$ obtained in this way, corresponding to

$\sigma_{12} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{smallmatrix} \right), \quad \sigma_{13} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{smallmatrix} \right), \quad \sigma_{14} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{smallmatrix} \right);$

$\sigma_{12} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{smallmatrix} \right), \quad \sigma_{13} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{smallmatrix} \right), \quad \sigma_{14} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{smallmatrix} \right);$

$\sigma_{12} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{smallmatrix} \right), \quad \sigma_{13} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{smallmatrix} \right), \quad \sigma_{14} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{smallmatrix} \right),$

respectively.

$The <img src='http://s0.wp.com/latex.php?latex=%5Cmathbb%7BZ%7D_2%5E2&bg=ffffff&fg=333333&s=0' alt='\mathbb{Z}_2^2' title='\mathbb{Z}_2^2' class='latex' /> coloring of <img src='http://s0.wp.com/latex.php?latex=A_3&bg=ffffff&fg=333333&s=0' alt='A_3' title='A_3' class='latex' /> corresponding to <img src='http://s0.wp.com/latex.php?latex=%5Csigma_%7B12%7D+%5Cequiv+%5Cleft%28%5Cbegin%7Bsmallmatrix%7D+1+%26+2+%26+3+%26+4+%5C%5C+2+%26+1+%26+4+%26+3+%5Cend%7Bsmallmatrix%7D+%5Cright%29%2C+%5Cquad+%5Csigma_%7B13%7D+%5Cequiv+%5Cleft%28%5Cbegin%7Bsmallmatrix%7D+1+%26+2+%26+3+%26+4+%5C%5C+3+%26+4+%26+1+%26+2+%5Cend%7Bsmallmatrix%7D+%5Cright%29%2C+%5Cquad+%5Csigma_%7B14%7D+%5Cequiv+%5Cleft%28%5Cbegin%7Bsmallmatrix%7D+1+%26+2+%26+3+%26+4+%5C%5C+4+%26+3+%26+2+%26+1+%5Cend%7Bsmallmatrix%7D+%5Cright%29.&bg=ffffff&fg=333333&s=0' alt='\sigma_{12} \equiv \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{smallmatrix} \right), \quad \sigma_{13} \equiv \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{smallmatrix} \right), \quad \sigma_{14} \equiv \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{smallmatrix} \right).' title='\sigma_{12} \equiv \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{smallmatrix} \right), \quad \sigma_{13} \equiv \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{smallmatrix} \right), \quad \sigma_{14} \equiv \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{smallmatrix} \right).' class='latex' />” width=”300″ height=”274″ /><p class=$ The $\mathbb{Z}_2^2$ coloring of $A_3$ corresponding to $\sigma_{12} \equiv \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{smallmatrix} \right), \quad \sigma_{13} \equiv \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{smallmatrix} \right),$ and $\sigma_{14} \equiv \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{smallmatrix} \right).$

For larger values of $n$ it is impractical to catalog the coherent color shift groups in silico via brute force: either a reasonably sophisticated algorithm or some (presumably nontrivial representation-theoretic) calculation in papyro is wanted. Nevertheless, it is easy to see that a cyclic coloring of $A_{n-1}$ exists for all $n$ (and hence that for $n$ prime the cyclic coloring is the only periodic $n$ -coloring): simply let

$s := \left(\begin{smallmatrix} 1 & 2 & \cdots & n-1 & n \\ 2 & 3 & \cdots & n & 1 \end{smallmatrix} \right).$

The cyclic coloring is obtained by setting $\sigma_{1k} := s^{k-1}.$

Color quotients and the cyclic color space

For $k \ge n$ we may consider a $k$ -coloring $\kappa$ of $A_{n-1}$ and the attendant color quotient $A_{n-1}/\sim$ , where $x \sim y \iff \kappa(x) = \kappa(y)$ . The color projection map $\Pi : A_{n-1} \rightarrow A_{n-1}/\sim$ is defined in the obvious way, and we may identify $\Pi$ and $\kappa$ with only a slight abuse of notation. In particular, if $\kappa$ is the cyclic coloring, the resulting color quotient is called the cyclic color space and denoted $\mathbb{A}_{n-1}.$

Consider a càdlàg random walk $\xi_t$ on $A_{n-1}$ , for $t \ge t_0 \equiv 0$ , and write $\kappa_t := \Pi \circ \xi_t \equiv \kappa \circ \xi_t$ for the projected walk on $\mathbb{A}_{n-1}.$ Let $t_\ell$ denote the $\ell$ th jump time of $\xi_t$ (and hence also $\kappa_t$ ), and in a further abuse of notation write $\kappa_\ell := \kappa(\xi_{t_\ell}).$ Let $j_\ell,k_\ell$ be defined via $\xi_{t_\ell} - \xi_{t_{\ell-1}} = -e_{j_\ell} + e_{k_\ell}.$ Now the color shift from $\kappa_\ell$ to $\kappa_{\ell+1}$ is

$\sigma_{\kappa_\ell \kappa_{\ell+1}} = \sigma_{\kappa_\ell 1} \sigma_{1 \kappa_{\ell+1}} = s^{1-\kappa_\ell}s^{\kappa_{\ell+1}-1} = s^{\kappa_{\ell+1}-\kappa_\ell}.$

Without loss of generality, let $\kappa_0 = 1$ and $\kappa(\xi_0-e_1+e_k) = k$ . Define

$\rho_n(m) := (m-1) \!\!\!\!\! \mod n + 1.$

Note that $s^\ell : j \mapsto s^\ell \cdot j \equiv \rho_n(j + \ell)$ , where $\cdot$ indicates the cyclic color shift action. Now

$\kappa(\xi_0-e_j+e_k) = \kappa([\xi_0-e_1+e_k]-e_j+e_1) \equiv \sigma_{j1} \cdot k$

$= \sigma_{1j}^{-1} \cdot k = s^{-j+1} \cdot k = \rho_n(k-j+1).$

Therefore $\kappa_1 = \rho_n(1+ k_1 - j_1)$ , and we have that the color shift from $\kappa_0$ to $\kappa_1$ is

$\sigma_{\kappa_0 \kappa_1} = s^{\kappa_1-\kappa_0} = s^{\rho_n(k_1 - j_1 + 1)-1} = s^{(k_1 - j_1) \!\!\!\!\! \mod n} = s^{k_1 - j_1}.$

We proceed along similar lines to compute $\kappa_{\ell+1}$ from $\kappa_\ell,$ $j_\ell,$ and $k_\ell:$

$\boxed{\kappa_{\ell+1} = \sigma_{j_\ell k_\ell} \cdot \kappa_\ell = s^{k_\ell - j_\ell} \cdot \kappa_\ell = \rho_n(k_\ell - j_\ell + \kappa_\ell).}$

This equation illustrates the ease and utility of projecting random walks from $A_{n-1}$ to $\mathbb{A}_{n-1}.$ It is also straightforward to show that for $a \in \mathbb{Z}^n$ the assignment

$\kappa \left( \sum_{m=1}^n a_m(-e_1 + e_m) \right) = \left( \sum_{m=1}^n a_m (m-1) \right) \!\!\!\!\! \mod n + 1$

produces the cyclic coloring.

In a followup post I’ll sketch how to identify the coherent color shift groups of low order and hint at some of the ways in which this construction might be applied.

Like this:

Be the first to like this post.

This entry was posted on Friday, August 21st, 2009 at 03:40 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 2

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

26 August 2009 at 22:40

[...] minimal periodic coloring theorem, part 3 Last time I gave nontrivial examples of periodic colorings of and demonstrated that the cyclic coloring of [...]

Reply

Equilibrium Networks