Transversals of symmetry classes |

Since a permutation of the arguments does not change the content, this setm^{n}_{l}:={pf_{l}=f_{l}o p^{-1}| pÎS_{n}}.

We would like to construct a transversal ofG\\m^{n}_{l}ÍG\\m^{n}.

Let us consider as an example the graphs on 4 vertices which contain exactly 2 edges, so thatf(i_{1})=...=f(i_{l1})=1, and i_{1}<...<i_{l1}.

According to the above arguments we have to find the orbits ofbar (12), bar (13), bar (14), bar (15), bar (16), bar (23), bar (24), bar (25), bar (26), bar (34), bar (35), bar (36), bar (45), bar (46), bar (56).

is the permutation group induced bybar (S_{4}):=S_{4}^{[2]}hookrightarrow S_{6}

and therefore one of the two orbits ofbar (S_{4})=á(24)(35),(1463)(25)ñ,

the other orbitw_{2}:={bar (16),bar (25),bar (34)},

The lexicographically smallest elements of these orbits *w _{1},w_{2}*
are the tabloids corresponding to

Hence the graphs shown below form a complete set of graphs on 4 vertices containing 2 edges!f=(1,1,1,1,2,2), and f'=(1,1,2,2,1,1).

The graphs with 4 vertices and 2 edges

This method is cumbersome, it can be used for
cataloging the graphs on *£7* vertices, say. We want therefore to describe
further refinements which allow to catalog the graphs with *v=10* vertices
(this is in fact the biggest *v*
for which a complete such list is available, there are approximately
*12·10 ^{6}* such graphs).

Having displayed an example in full, let us go into detail in
order to make the procedure of finding the minimal representatives more
efficient. Recall that we have to check if a given *f* is the
lexicographically smallest element in its orbit, i.e. if the following is
true:

The verification of this condition is one of the crucial parts of the whole procedure. Let us call this check the" sÎbar (G):f£f o s, for short: f£bar (G)(f).

and we assume that left coset representatives{1}=C_{bar (G)}(b)£C_{bar (G)}(b-1)£...£C_{bar (G)}(0)=bar (G),

Thus, in order to apply the minimality test, we have to run through the elements ofC_{bar (G)}(i-1)=È_{j=1}^{r(i)}p_{j}^{(i)}C_{bar (G)}(i), where p_{1}^{(i)}ÎC_{bar (G)}(i).

This means that in order to applys=p_{j1}^{(1)}...p_{jb}^{(b)}.

It is very important to cut this tree down as much as possible. This can be done, for example, by an application of

Proof: ForLemma:Iff<f o pand_{j}^{(i)}f(i)<f o p, then we have, for the orbit of_{j}^{(i)}(i)funder the action ofC:_{bar (G)}(i) £bar (G)f<C_{bar (G)}(i)(f o p_{j}^{(i)}).

whilef o p_{j}^{(i)}o t^{-1}(k)=f(k),

f o p_{j}^{(i)}o t^{-1}(i)= f o p_{j}^{(i)}(i)>f(i).

This result allows us to
*cut off the branch starting with the element*
*...p _{j}^{(i)}* from the tree
formed by the elements of

Besides this we can choose a suitable *way in which we work through the
tree* in order to find
the smallest element in the orbit *G(f)*. A remark that will
lead us to a good such choice makes use of the fact that *fÎ m^{n}* will not in general be injective.
But in this case there exist

We can therefore subdivides^{-1}C_{bar (G)}(i)(f)= t^{-1}C_{bar (G)}(i)(f).

Correspondingly we shall run throughbar (G)=È_{i=1}^{b}(C_{bar (G)}(b-i)\C_{bar (G)}(b-i+1))È{1}.

- [1.]
*C*,_{bar (G)}(__b-1__)\C_{bar (G)}(__b__) - [2.]
*C*,_{bar (G)}(__b-2__)\C_{bar (G)}(__b-1__) - []
*vdots* - [b.]
*C*._{bar (G)}(Æ)\C_{bar (G)}(__1__)

if we hadC_{bar (G)}(i-1)\C_{bar (G)}(i) =È_{j=2}^{r(i)}p_{j}^{(i)}C_{bar (G)}(i),

and note that, for eachA:={rÎbar (G) | f o r=f} £bar (G),

A transversal of the set of left cosetsC_{A}(i)£C_{bar (G)}(i).

Proof: IfLemma:If we denote byJ(i)the setand if we fix, for eachJ(i):={jÎr(i)| $s_{j}ÎC_{bar (G)}(i) :p_{j}^{(i)}s_{j}ÎA},jÎJ(i), such an elements, then_{j}is a transversal of{t_{j}:=p_{j}^{(i)}s_{j}| jÎJ(i)}C._{A}(i-1)/C_{A}(i)

Another byproduct is the following test:Corollary:The setyields the Sims chain of the stabilizer{t_{j}=p_{j}^{(i)}s_{j}| jÎJ(i)}Aoff.

Let us now summarize what has been said so far about the minimality test which we have to carry out in order to find the lexicographically smallest element of the orbitCorollary:If, for eachi,j,f'(i) not =f o p, then_{j}^{(i)}(i)f' not ÎG(f).

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001

Transversals of symmetry classes |