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);

or

\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);

or

\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 \ellth 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.

2 Responses to A minimal periodic coloring theorem, part 2

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

    • Carley says:

      Hooray for new traditions. I was srisruped to learn you all hadn’t put up a tree before. We almost didn’t this year last year’s tree dropped so many needles and I wasn’t sure I could handle that again. We went with a different tree variety this year, and it’s been much better so far.

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 )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: