Equilibrium Networks

Last time I gave nontrivial examples of periodic colorings of and demonstrated that the cyclic coloring of exists for all More generally for composite, let for a group of order (By Cayley’s theorem, every finite group can be realized in this way.) Then In other words, every finite group of order can be realized as a minimal periodic coloring of

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 to color )

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

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 , where the standard basis is indicated, and are respectively one of source or destination attributes that characterize the packet. These sorts of vectors generate (For reasons outlined in a whitepaper of ours [see our website] 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).

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.