[Nauty] Searching for automorphisms of only one colour

[Brendan McKay]

* Christopher Jefferson <caj at cs.york.ac.uk> [021015 01:10]:
> >Without knowing the graph structure I can't be sure I'm answering
> >the right question.  Is this the problem:
> >   There may be symmetries amongst the relations even when the
> >   variables are all fixed, and you don't want such symmetries
> >   to appear in the nauty output. ??
> >Is it true by any chance that the relation vertices are only
> >joined to variable vertices?  And vice-versa?
> 
> Yep, relations are only joined to variables, and variables to relations, so 
> actually the graph is bi-pirate (I hadn't noticed before...) with the 
> variables in one part and the relations in the other. However it is still 
> important that some relations are different colours to one each another.
> 
> In fact, I want something stronger, I want only those symmetries that only 
> permute variables. I can do this by finding all the symmetries and then 
> "stabilizing" all the relations one by one. However, it might be possible 
> to do it faster?

Ok.  So let's say you have a bipartite graph with parts X and Y.
The vertices are coloured, but the same colour can't occur in both
X and Y.  Consider three groups:
  G = full (colour-preserving) automorphism group of the graph
  G_X = the part of G which fixes each vertex in X.
  H = the action of G on X
nauty will give you generators for G, but your application requires
generators for H.

Firstly, it is NOT GUARANTEED that the generators found by nauty
include a subset generating G_X.  So you can't just look for those
generators and cross them off.  It is possible (using usertcellproc)
to force this behaviour, but there is a better way to get H.

If two or more Y vertices have the same colour and the same
neighbours in X (call them "equivalent Y vertices"), then you can
swap them with each other while fixing everything else.  This gives
an element of G_X.
The key observation is:  ALL of G_X arises in this way.

The most efficient way to solve your problem is to make a
different graph.  Replace each set of equivalent Y vertices
by a single vertex.  The colour of the new vertex should reflect
the colour of the original vertices and the number of original
vertices that are being replaced.  Then the full automorphism group
of the new graph is what you want.

Suppose X = {0,1,2,3}, Y = {4,5,6,7,8,9} with
  vertex  colour  neighbours
    4       A        0,1
    5       B        1,2,3
    6       B        0,1
    7       B        1,2,3
    8       A        0,1
    9       B        1,2,3
The classes of equivalent Y vertices are {4,8}, {5,7,9}, {6}.
The new graph has X = {0,1,2,3}, Y' = {4,5,6} with
    4       A2       0,1   (replacing old 4 and 8)
    5       B3       1,2,3 (replacing old 5, 7, 9)
    6       B1       0,1   (replacing old 6)

The new graph has the property that fixing each vertex in X
fixes the whole graph.  Therefore, the X parts of the generators
given by nauty are a non-redundant set of generators for H.

If there is some reason you can't make a new graph, it is possible
to achieve the same effect by colouring.  The order of the vertices
within each class of equivalent Y vertices is immaterial so you can
impose an arbitrary order on them:
    4       Aa       0,1
    5       Ba       1,2,3
    6       Ba       0,1
    7       Bb       1,2,3
    8       Ab       0,1
    9       Bc       1,2,3
(Within each set of equivalent Y vertices, I have arbitrarily
assigned a,b,c,... ).
However this graph is larger so nauty will probably be a bit slower.

The "best" way to handle your problem would be to regard it as
a hypergraph with vertices {0,1,2,3} and a hyperedge for each
relation.  This will be possible in a future release of nauty.
The main change in this release was to reorganise the code to
smooth the way for things like this.  As well as hypergraphs,
nauty will be able to handle matrices and large sparse graphs,
graphs with coloured edges, and perhaps other things.

> Also, one small thing that did not occur to me before, but I expect is OK. 
> I tried to find a definition of isomorphism on graphs with coloured 
> vertices and could not find one. I am assuming that (trivial case) if I 
> have 4 vertices, 1,2,3,4 s.t. 1 is connected to 2, and 3 is connected to 4, 
> and they are split into colour groups {1,2} , {3} , {4}, then there is no 
> automorphisms? (so I can't do (1,2) ).

Sure you can do (1 2).  Vertices 1 and 2 have the same colour.
However, (3 4) is not allowed as vertices 3 and 4 have different colour.
The group consists of all permutations on the vertex set such that
edges are mapped onto edges, and vertices are mapped onto vertices
of like colour.

> If there are two colour groups with the same number of vertices, could the
> two groups get swapped around? I don't want this to happen, I want each
> vertex to end up being the same colour.

No, they can't get swapped around.  Vertices are only swapped around
inside each colour class.  (Btw, avoid using "group" for anything
that is not a group in the algebraic sense.)
 
Brendan.