# Equilibrium Networks

Science, networks, and security

## A minimal periodic coloring theorem, part 3

Last time I gave nontrivial examples of periodic colorings of $A_3,$ and demonstrated that the cyclic coloring of $A_{n-1}$ exists for all $n.$ More generally for $n$ composite, let $\{ \sigma_{1k} \}_{k=1}^n \cong G$ for a group $G$ of order $n.$ (By Cayley’s theorem, every finite group can be realized in this way.) Then $\Gamma_\sigma \cong G.$ In other words, every finite group of order $n$ can be realized as a minimal periodic coloring of $A_{n-1}.$

It’s not immediately clear to me that every minimal periodic coloring arises in this way, but I would bet on it. (The first person who can demonstrate this is welcome to claim \$.50 and a Sprite as reward, and an equal reward goes for the first person who can provide some kind of actual picture of what happens with a nonabelian example, say using $S_3$ to color $A_5.$)

Making the connection practically is a bit more involved. I did the simple thing and used permutation matrices to look for faithful representations of finite groups. First up is the code to produce a product of two permutations:

```function y = permprod(s1,s2)
% Product of permutations.
% s1 and s2 represent permutations in $S_n$ as arrays (akin to the two-row
% notation and NOT cycle decomposition).
% This function maps s1 and s2 to permutation matrices, computes their
% product, and returns the corresponding array.
if size(s1,1)*size(s2,1) - 1
  'needs row arrays'
  return;
elseif size(s1,2)-size(s2,2)
  'sizes must match'
  return;
else
  n = size(s1,2);
end

I = eye(n);

% permutation matrices
m1 = I(s1,:); m2 = I(s2,:);
m = m1*m2;

% now deduce the array
for j = 1:n
  s(j) = find(m(j,:),1);
end

y = s;```

and next the inverse of a permutation:

```function y = perminv(s1)
% Inverse permutation.
% s1 represents permutation in $S_n$ as an array (akin to the two-row
% notation and NOT cycle decomposition).
% This function maps s1 to a permutation matrix, computes its inverse,
% and returns the corresponding array.

if size(s1,1) - 1
  'needs row array'
  return;
else
  n = size(s1,2);
end

I = eye(n);

% permutation matrix
m1 = I(s1,:);
m = inv(m1);

% now deduce the array
for j = 1:n
  s(j) = find(m(j,:),1);
end

y = s;```

and finally a very crude way to see which choices of permutations produce coherent color shift groups and which don’t:

```function y = colorshiftcheck(varargin)
% Consider elements sjk (or $\sigma_{jk}$) of $S_n$ for 1 ≤ j,k ≤ n and
% subject to the following defining relations:
% 1) sjk*skj = e
% 2) sjk*skl = sjl
% This code starts with $n-1$ permutations s12,...,s1n and proceeds to
% determine whether 1) and 2) hold

% inputs are s12,...,s1n

n = length(varargin)+1;

% get the s1j and check their size, then compute the inverses sj1
for j = 2:n
  temp = varargin(j-1);
  s{1,j} = temp{1};
  if size(s{1,j},2)-n
    j-1
    'th entry length incorrect'
    break;
  elseif size(s{1,j},1)-1
    j-1
    'th entry has too many rows'
    break;
  end
  s{j,1} = perminv(s{1,j});
end

s{1,1} = 1:n;
% form the entries sjk=sj1*s1k
for j = 2:n
  for k = 2:n
    s{j,k} = permprod(s{j,1},s{1,k});
  end
end

% now check to see that the assignments s{j,k} are consistent:
for j = 2:n
  for k = 2:n
    if sum(abs( perminv(s{k,j}) - s{j,k} ))
      'inverse failure at'
      [j k]
    end
    for l = 2:n
      if sum(abs( permprod(s{j,l},s{l,k}) - s{j,k} ))
        'product failure at'
        [j k l]
      end
    end
  end
end

y = s;```

There are probably much more sophisticated ways to do this sort of thing, but the overall idea should be clear: you can specify a symmetry group you want to be reflected in a minimal periodic coloring, and combine these if you want nonminimal periodic colorings (another \$.50 and a Sprite go to the first person who demonstrates that every nonminimal periodic coloring is either obtained in this way or provides a counterexample). For example, combining the two colorings shown last time produces a periodic 8-coloring of $A_3.$

The reason we looked at this sort of thing at Equilibrium is (briefly) that it is possible to make individual packets correspond to vectors of the form $-e_j + e_k$, where the standard basis is indicated, and $j, k$ are respectively one of $n$ source or destination attributes that characterize the packet. These sorts of vectors generate $A_{n-1}.$ (For reasons outlined in a whitepaper of ours [see our website] $n$ can generally be taken to be quite small.) The idea then was to take the induced trajectory (here, the sequence of colors) corresponding to a sequence of observed packets and use various tools from probability to characterize the network traffic (a real explanation of this will have to wait for future posts, as will an explanation of how we can do something along these lines without using the coloring theorem).

### Like this:

This entry was posted on Wednesday, August 26th, 2009 at 22:40 and is filed under Communications security, 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.

### 2 Responses to A minimal periodic coloring theorem, part 3

1. [...] translating network packets to random walks was similar to the approach described at the end of a previous post, except that the finite space is used instead of the infinite root lattice ), and we seriously [...]

2. Mary says:

So I’m not sure if the contest is still going . but I thguoht I’d add my 2 cents!1. Best hole-in-the-wall Raleigh eatery:The Bull and Bear (Millbrook and Six Forks)Good southern breakfast cookin at a great price, with decor that hasn’t changed since the 70 s. Guaranteed you will be the only person under 50!2. Best authentic eastern barbeque:Connor’s in downtown RaleighfanTAStic barbeque that’s been around longer than I have!3. Best unconventional date place:The NC Museum of Natural ScienceGreat exhibits and FREE!4. Best thing to do on a Sunday afternoon:The Falls Lake trail systemThese trails are in North Raleigh and are a little outdoor treasure for the city!5. Newest coffee phenom:The Coffee-shaw (from Raleigh Rickshaw)Raleigh Rickshaw created a coffee cart, complete with stools and a pretty full drink menu! Find it downtown in various locations!

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 18, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.905105471611023, "perplexity_flag": "middle"}