Recursion and orderly generation

Recursion and orderly generation

Lemma: Assume an action _GX, and that BÍX is a block or, as it is sometimes called a system of imprimitivity (which means that B is mapped under gÎG either onto B or onto a subset gB which is disjoint with B). Then the following is true:

• For each orbit wÎG\\X we have

  wÇB not =Æ iff wÇgB not =Æ,

  which means that B and gB intersect with the same orbits.
• For each bÎB, gÎG, gbÎB is true if and only if

  gÎN_G(B):={gÎG | gB=B}.

Therefore, if

X=È_iÎIB_i,

a disjoint union of blocks, and JÍI such that

T(G\\{B_i | iÎI})={B_j | jÎJ}

is a transversal of G on the set of these blocks, then a transversal T(G\\X) is the following union of transversals:

T(G\\X)=È_jÎJT(N_G(B_i)\\B_i),

where T(N_G(B_i)\\B_i) is an arbitrary transversal of N_G(B_i)\\B_i.

 The Homomorphism Principle Assume that G acts on the sets X_i, i=1,2, and that j:X₂ -> X₁ commutes with the action:

j(gx₂)=gj(x₂), for each gÎG,x₂ÎX₂,

then each inverse image j^-1(x₁),x₁ÎX₁, is a block. Moreover, the normalizer of this block is the stabilizer of x₁:

N_G(j^-1(x₁))=G_x1.

 Surjective Resolution Assume that G acts on the sets X_i,iÎm, and that we are given surjective mappings

j_i+1:X_i+1 -> X_i, for each iÎm-1,

that commute with the action:

j_i+1(gx_i+1)=gj_i+1(x_i+1), for each iÎm-1, gÎG,x_i+1ÎX_i+1.

Then we can obtain a transversal T of G\\X_m by successively working backwards, starting by evaluating a transversal of G\\X₁ and the stabilizers of its elements, and then evaluating the inverse images j₂(x) of the elements x in this transversal, as well as the transversals G_x\\j₂^-1(x), and so on, in accordance with the lemma.

Example: For sake of simplicity we assume that

Y^X=mⁿ,

and that G acts on n and so on Y^X=mⁿ in the canonic way.

The Surjective Resolution method can be applied since the following mapping commutes with the action of G on the G-sets kⁿ:

j_k:kⁿ -> (k-1)ⁿ:f -> f',

where f' is defined by

f'(i):=f(i) if f(i)Îk-1

f'(i):=k-1 otherwise.

We can therefore start from X₁:=1ⁿ, which consists of the single and constant mapping i -> 1, iÎn. The stabilizer is G, and the inverse image is the whole set X₂:=2ⁿ. We therefore have to evaluate in this second step a transversal T₂ of G\\2ⁿ. Assume that this is done, and let f₂ denote an element of T₂, G_f2 its stabilizer. It remains to evaluate in the third step, for each such f₂ and its stabilizer a transversal T₃ of

G_f2\\j₃^-1(f₂).

This inductive step can be carried out as follows. Two elements f₃ and f₃' of j₃^-1(f₂) can differ only on the inverse image f₂^-1(2) of the point 2, and the values there can only be 2 or 3. We therefore need only to evaluate a transversal T of

G_f2\\{2,3}^f₂-1(2).

The desired transversal T₃ then consists of the mappings f₃"Î3ⁿ such that

f₃" | _f2^-1(2)ÎT, and f₃" | _n\f2^-1(2)=f₂ | _n\f2^-1(2).

T_>(G\\Y^X),

Example: Recall that the graphs on v vertices correspond to the set of orbits

S_v\\2^{v choose 2}.

As v is totally ordered, so is the set of pairs v choose 2, and hence also the set of labelled graphs. This is in fact the lexicographic order £ on the set of 0-1-sequences obtained from the adjacency matrices by reading the upper triangular part row by row from left to right and from top to bottom. For example is mapped onto the sequence (1,1,0,0,1,0), and hence this labelled graph is a member of the canonic transversal, but (0,0,1,1,1,0), which corresponds to the isomorphic labelled graph is not a canonic representative.

The problem of orderly generation now means the following. We would like to find an economic way of generating 0-1-sequences of length 6 in such a way that not too many sequences are generated, which do not correspond to the desired canonic representatives. Moreover, we should like to do this by increasing the number of ones successively by 1, which means by successively increasing the number of edges.

One way of doing this is to start off from the sequence (0,0,0,0,0,0), which forms the canonic transversal of the labelled graphs of total weight 0:

T_>⁽⁰⁾={(0,0,0,0,0,0)}.

Now we will evaluate T_>⁽¹⁾, then T_>⁽²⁾, and so on, in the following way. Assume that T_>⁽ⁱ⁾ is at hand. Then, in order to obtain T_>⁽ⁱ⁺¹⁾, we shall apply to each member of T_>⁽ⁱ⁾ the following augmentation. We change in each element of T_>⁽ⁱ⁾ in all the possible ways just one entry zero that is to the right of the rightmost entry 1. The resulting set of labelled graphs is either empty, if no such entry exists, or it consists of labelled graphs with one more edge. These sets have to be checked carefully, the canonic sequences have to be kept, the others have be thrown away before going to the next step. The remaining set of labelled graphs is in fact the desired transversal T_>⁽ⁱ⁺¹⁾. In our example this process runs as follows:

• [1.] In the first step we get the six sequences containing exactly one entry 1. The canonic respresentative is, of course, (1,0,0,0,0,0), and so, clearly

  T_>⁽¹⁾={(1,0,0,0,0,0)}.

• [2.] In the second step we start with (1,0,0,0,0,0) and obtain, after canceling the sequences which are not canonic, that

  T_>⁽²⁾={ (1,1,0,0,0,0),(1,0,0,0,0,1)}.

• [3.] The third step gives, from the first canonic representative of the second step, the sequences (1,1,1,0,0,0), (1,1,0,1,0,0) and (1,1,0,0,0,1), while the other representative of T_>⁽²⁾ needs not to be considered, as there is no zero entry to the right of the rightmost entry 1. Thus

  T_>⁽³⁾={(1,1,1,0,0,0),(1,1,0,1,0,0),(1,1,0,0,0,1)}.

• [4.] In the fourth step we get (1,1,1,1,0,0), from the first element of T_>⁽³⁾, nothing new from the second one, but (1,1,0,0,1,1) from the third element, and hence

  T_>⁽⁴⁾={(1,1,1,1,0,0),(1,1,0,0,1,1)}.

• [5.] The next step gives

  T_>⁽⁵⁾={(1,1,1,1,1,0)},

  from which we obtain in
• [6.] the final step that

  T_>⁽⁶⁾={(1,1,1,1,1,1)}.

  And so, summing up, we have obtained the desired canonic transversal of the isomorphism classes of labelled graphs on 4 vertices:

  T_>={(0,0,0,0,0,0),(1,0,0,0,0,0),(1,1,0,0,0,0),

  (1,0,0,0,0,1), (1,1,1,0,0,0),(1,1,0,1,0,0),(1,1,0,0,0,1),

  (1,1,1,1,0,0),(1,1,0,0,1,1),(1,1,1,1,1,0), (1,1,1,1,1,1)}.

Theorem: (Read) Assume a finite action _GX where X is totally ordered by £ and a disjoint union

X=Èⁿ_i=1X_i,

of invariant and nonempty subsets X_i. Let A denote an algorithm that produces for each xÎX either the empty set or a set A(x)ÍX in descending order, such that the following conditions hold for the canonic transversals T_>⁽ⁱ⁾ of the orbit sets G\\X_i, for each iÎn-1:

• T_>⁽ⁱ⁺¹⁾ÍÈA(x), union over the xÎT_>⁽ⁱ⁾},
• for each xÎT_>⁽ⁱ⁺¹⁾ there exists a unique element x'ÎT_>⁽ⁱ⁾ such that xÎA(x'), and finally,
• for any x₁,x₂ÎT_>⁽ⁱ⁺¹⁾, x₁<x₂, we have the implication

  x₁ÎA(x'₁),x₂ÎA(x'₂) imply x'₁<x'₂.

Then, computing T_>⁽¹⁾ and recursively running through T_>⁽ⁱ⁾ with x, producing the augmentation A(x), and eliminating representatives which are not canonic from A(x), for iÎn-1, gives the desired canonic transversal T_> of G\\X as the following union:

T_>=È_i=1ⁿT_>⁽ⁱ⁾.

This orderly generation obviously will work as soon as we have found an augmentation procedure A that has the properties listed in the items of the above theorem of Read. We already saw such an augmentation that can be used for the graphs and which amounts to adding an edge in a certain set of places. The necessary canonicity test can be done quite efficiently using any suitable invariant that allows to put the canonic representatives in what is called an AVL-tree in computer science. For example, in the molecular graphs case, we can use a so-called Morgan table, which is a numbering well known to chemists, and used in the coding procedure for chemical substances in the Chemical Abstracts. It reduces the set of checks to a reasonable small number.

Summing up we should like to mention that an efficient way of evaluating a transversal of the symmetry of G on Y^X can be implemented by using the following methods:

• A recursion procedure, using recursion on | Y | .
• Read's orderly generation, by applying lexicographic or any other ordering of Y^X.
• A canonic form of the elements fÎY^X which allows to put the canonic representatives (canonic with respect to the ordering mentioned in the second item) together into an AVL-tree and which reduces the necessary number of checks to a reasonably small one.

Exercises

E: Check the lemma.

Recursion and orderly generation