Transversals of symmetry classes |

In this section we shall restrict attention to a redundancy free construction
of a transversal of the *G*-classes on *Y ^{X}:=m^{n}*. Moreover, in order to
decrease the complexity we restrict attention to

m^{n}_{l}:={pf_{l}=f_{l}o p^{-1}| pÎS_{n}}.

Since a permutation of the arguments does not change the content, this set
* m^{n}_{l} * is a union of orbits of

G\\m^{n}_{l}ÍG\\m^{n}.

We would like to construct a transversal of * m^{n}_{l} *. This reduces the complexity
since the desired transversal of

f(i_{1})=...=f(i_{l1})=1, and i_{1}<...<i_{l1}.

Let us consider as an example the graphs on 4 vertices which contain exactly
2 edges, so that *n=
4 choose 2=6*, *m=2*, and *l=(4,2)*.
Before we write down all the 15 *(4,2)*-tabloids
in full detail, it is practical to note that in each tabloid the first
(or any other) row
is uniquely determined by the remaining rows which form the
*truncated*
tabloid.
Hence in the present case we need only to display the second rows, here they
are:

bar (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).

According to the above arguments we have to find the orbits of
*bar (S _{4})* on this set.
Recall that the elements

bar (S_{4}):=S_{4}^{[2]}hookrightarrow S_{6}

is the permutation group induced by *S _{4}=á(12),(1234)
ñ* on this set of pairs of vertices. Thus

bar (S_{4})=á(24)(35),(1463)(25)ñ,

and therefore one of the two orbits of *bar (S _{4})* on the
set of

w_{2}:={bar (16),bar (25),bar (34)},

the other orbit *w _{1}* consists of the remaining 12 truncated tabloids.
(Note that in a preprocessing calculation we can obtain, by an application
of the enumeration
theory described above, that the number of graphs with 4 vertices and 2 edges
is

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

f=(1,1,1,1,2,2), and f'=(1,1,2,2,1,1).

Hence the graphs shown below form a complete set of graphs on 4 vertices containing 2 edges!

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:

" sÎbar (G):f£f o s, for short: f£bar (G)(f).

The verification of this condition is one of the crucial parts
of the whole procedure. Let us call this check the *minimality test*
for *f*. In order to
carry it out in a reasonable way we recall what has been said about Sims
chains. Assume that * b * is the base for the action of

{1}=C_{bar (G)}(b)£C_{bar (G)}(b-1)£...£C_{bar (G)}(0)=bar (G),

and we assume that left coset representatives *p _{j}^{(i)}* ar at hand such
that

C_{bar (G)}(i-1)=È_{j=1}^{r(i)}p_{j}^{(i)}C_{bar (G)}(i), where p_{1}^{(i)}ÎC_{bar (G)}(i).

Thus, in order to apply the
minimality test, we have to run
through the elements of *bar (G)*, each of which can uniquely be written in the
form

s=p_{j1}^{(1)}...p_{jb}^{(b)}.

This means that in order to apply *each* element of *bar (G)* to
*f*, say, we have to run through the following tree:

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

Lemma: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)}).

Proof: For *tÎC _{bar (G)}(i)* and

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

while

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

s^{-1}C_{bar (G)}(i)(f)= t^{-1}C_{bar (G)}(i)(f).

We can therefore subdivide *bar (G)* according to the Sims chain and the
base * b *:

bar (G)=È_{i=1}^{b}(C_{bar (G)}(b-i)\C_{bar (G)}(b-i+1))È{1}.

Correspondingly we shall run through *bar (G)* (in any case, whether
*f* is injective or not) by working through the following
subsets, one row after the other, from top to bottom:

- [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__)

The identity element can be left out since *f o 1=
f*. We note that in step number *b-i+1* we are running
through the set

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

if we had *f£C _{bar (G)}(i)
(f)*
before, assuming that

A:={rÎbar (G) | f o r=f} £bar (G),

and note that, for each *iÎ b *:

C_{A}(i)£C_{bar (G)}(i).

A transversal of the set of left cosets
*C _{A}(i-1)/C_{A}(i)* can be
obtained from the transversal

Lemma: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)

Proof: If *sÎC _{A}(i)*, then, by
the formula, there
exists a

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

Another byproduct is the following test:

Corollary:If, for eachi,j,f'(i) not =f o p, then_{j}^{(i)}(i)f' not ÎG(f).

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
orbit *G(f)*. We discussed the Sims chain for the action
of *G* on * n*, it leads to the tree, and we saw
in the lemma that certain cuts and
jumps can be made while running through this tree. But still
this does

harald.fripertinger "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

Transversals of symmetry classes |