Algebraic Combinatorics -- Transversals of symmetry classes

Transversals of symmetry classes

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ⁿ. Moreover, in order to decrease the complexity we restrict attention to G-classes of fixed content l=(l₁,...) n, starting off from the canonic mapping f with this content:

The set of all the mappings of this content will be indicated as follows:

mⁿ_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ⁿ_l is a union of orbits of G on mn :

G\\mⁿ_l ÍG\\mⁿ .

We would like to construct a transversal of mⁿ_l . This reduces the complexity since the desired transversal of G\\mⁿ is the union of the transversals of the sets G\\mⁿ_l , taken over all the l n. The crucial point is now that in each orbit of G on mⁿ_l there is a unique representative which is the lexicographically smallest element of its orbit. Therefore we may call these lexicographically smallest elements a canonic transversal of G\\mⁿ_l . A mapping fÎmⁿ_l can be displayed by its l-tabloid

where we put the elements of the inverse image f^-1[{k}] of kÎm into the k-th row, in increasing order, so that e.g.

f(i₁)=...=f(i_l₁)=1, and i₁<...<i_l₁.

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₄) on this set. Recall that the elements 1,...,6Î6 on which S₆ acts, stand for the pairs {1,2},...,{5,6} of vertices. The subgroup

bar (S₄):=S₄^[2] hookrightarrow S₆

is the permutation group induced by S₄=á(12),(1234) ñ on this set of pairs of vertices. Thus

bar (S₄)=á(24)(35),(1463)(25)ñ,

and therefore one of the two orbits of bar (S₄) on the set of (4,2)-tabloids is

w₂:={bar (16),bar (25),bar (34)},

the other orbit w₁ 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 two, a result which is very helpful as stopping rule, as the present example already shows!)

The lexicographically smallest elements of these orbits w₁,w₂ are the tabloids corresponding to bar (56)Îw₁ and bar (34)Îw₂. These tabloids are The corresponding mappings f,f'Î2⁶ are

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⁶ 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 bar (G) on n (still fÎmⁿ ), so that

{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⁽ⁱ⁾ ar at hand such that

C_{bar (G)}(i-1)=È_j=1^r(i)p_j⁽ⁱ⁾ C_{bar (G)}(i), where p₁⁽ⁱ⁾Î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_j₁⁽¹⁾...p_{j_b}^(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: If f<f o p_j⁽ⁱ⁾ and f(i)<f o p_j⁽ⁱ⁾(i), then we have, for the orbit of f under the action of C_{bar (G)}(i) £bar (G):
f<C_{bar (G)}(i)(f o p_j⁽ⁱ⁾).

Proof: For tÎC_{bar (G)}(i) and kÎi-1 we have

f o p_j⁽ⁱ⁾ o t^-1(k)=f(k),

while

f o p_j⁽ⁱ⁾ o t^-1(i)= f o p_j⁽ⁱ⁾(i)>f(i).

This result allows us to cut off the branch starting with the element ...p_j⁽ⁱ⁾ from the tree formed by the elements of bar (G).

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ⁿ will not in general be injective. But in this case there exist t,sÎS_n \{1} such that f o s=f o t, and so we have for each iÎn the equation

s^-1C_{bar (G)}(i)(f)= t^-1C_{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⁽ⁱ⁾C_{bar (G)}(i),

if we had f£C_{bar (G)}(i) (f) before, assuming that p₁⁽ⁱ⁾=1, for each i, so that we can always start with j=2. This way to procede allows to use the following remark: In the case when there exists any sÎC_{bar (G)} (i) for which f o p_j⁽ⁱ⁾ o s= f, then p_j⁽ⁱ⁾C_{bar (G)}(i)(f)³f, and so we can jump over the whole coset p_j⁽ⁱ⁾C_{bar (G)} (i), by the formula. This idea can also be used in order to derive the Sims chain of the stabilizer of f. Let us indicate this stabilizer as follows:

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 {p_j⁽ⁱ⁾ | jÎr(i)} of C_{bar (G)}(i-1)/C_{bar (G)}(i) in the following way:

Lemma: If we denote by J(i) the set
J(i):={jÎr(i) | $s_jÎC_{bar (G)}(i) :p_j⁽ⁱ⁾s_jÎA},
and if we fix, for each jÎJ(i), such an element s_j, then
{t_j:=p_j⁽ⁱ⁾s_j | jÎJ(i)}
is a transversal of C_A(i-1)/C_A(i).

Proof: If sÎC_A(i), then, by the formula, there exists a jÎr(i) such that sÎp_j⁽ⁱ⁾C_{bar (G)} (i), so that this j must lie in J(i). Moreover the left cosets t_jC_A(i) are pairwise different, since the formula holds.

Corollary: The set
{t_j=p_j⁽ⁱ⁾s_j | jÎJ(i)}
yields the Sims chain of the stabilizer A of f.

Another byproduct is the following test:

Corollary: If, for each i,j, f'(i) not =f o p_j⁽ⁱ⁾(i), then
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 not suffice to carry out this test in an efficient way, say if we want to catalog the graphs on 10 vertices. We shall therefore continue by considering the evaluation of the orbits of the centralizers C_{bar (G)}(i).

harald.fripertinger@kfunigraz.ac.at,
last changed: August 28, 2001

Transversals of symmetry classes