Recursion and orderly generation |

The checks are easy and left as an exercise. This result shows that the direct evaluation of a transversal can be replaced by successive evaluations of blocks, their normalizers and transversals of the orbits of the normalizers on the blocks. An interesting method systematically to obtain blocks can be derived fromLemma:Assume an action, and that_{G}XBÍXis ablockor, as it is sometimes called asystem of imprimitivity(which means thatBis mapped undergÎGeither ontoBor onto a subsetgBwhich is disjoint withB). Then the following is true:Therefore, if

- For each orbit
wÎG\\Xwe havewhich means thatwÇB not =Æ iff wÇgB not =Æ,BandgBintersect with the same orbits.- For each
bÎB, gÎG,gbÎBis true if and only ifgÎN_{G}(B):={gÎG | gB=B}.a disjoint union of blocks, andX=È_{iÎI}B_{i},JÍIsuch thatis a transversal ofT(G\\{B_{i}| iÎI})={B_{j}| jÎJ}Gon the set of these blocks, then a transversalT(G\\X)is the following union of transversals:whereT(G\\X)=È_{jÎJ}T(N_{G}(B_{i})\\B_{i}),T(Nis an arbitrary transversal of_{G}(B_{i})\\B_{i})N._{G}(B_{i})\\B_{i}

This is easy to check but very important to remark since it is essential forThe Homomorphism PrincipleAssume thatGacts on the setsX,_{i}i=1,2, and thatj:Xcommutes with the action:_{2}-> X_{1}then each inverse imagej(gx_{2})=gj(x_{2}), for each gÎG,x_{2}ÎX_{2},jis a block. Moreover, the normalizer of this block is the stabilizer of^{-1}(x_{1}),x_{1}ÎX_{1},x:_{1}N_{G}(j^{-1}(x_{1}))=G_{x1}.

We would like now to apply this to symmetry classes in order to obtain a recursive evaluation of a transversal, using recursion onSurjective ResolutionAssume thatGacts on the setsX, and that we are given surjective mappings_{i},iÎmthat commute with the action:j_{i+1}:X_{i+1}-> X_{i}, for each iÎm-1,Then we can obtain a transversalj_{i+1}(gx_{i+1})=gj_{i+1}(x_{i+1}), for each iÎm-1, gÎG,x_{i+1}ÎX_{i+1}.TofG\\Xby successively working backwards, starting by evaluating a transversal of_{m}G\\Xand the stabilizers of its elements, and then evaluating the inverse images_{1}jof the elements_{2}(x)xin this transversal, as well as the transversalsG, and so on, in accordance with the lemma._{x}\\j_{2}^{-1}(x)

The method of Surjective Resolution can be combined with the method ofExample:For sake of simplicity we assume thatand thatY^{X}=m^{n},Gacts onand so onnYin the canonic way.^{X}=m^{n}The Surjective Resolution method can be applied since the following mapping commutes with the action of

Gon theG-sets:k^{n}wherej_{k}:k^{n}-> (k-1)^{n}:f -> f',f'is defined byf'(i):=f(i) if f(i)Îk-1We can therefore start fromf'(i):=k-1 otherwise.X, which consists of the single and constant mapping_{1}:=1^{n}i -> 1, iÎ. The stabilizer isnG, and the inverse image is the whole setX. We therefore have to evaluate in this second step a transversal_{2}:=2^{n}Tof_{2}G\\. Assume that this is done, and let2^{n}fdenote an element of_{2}T,_{2}Gits stabilizer. It remains to evaluate in the third step, for each such_{f2}fand its stabilizer a transversal_{2}Tof_{3}This inductive step can be carried out as follows. Two elementsG_{f2}\\j_{3}^{-1}(f_{2}).fand_{3}fof_{3}'jcan differ only on the inverse image_{3}^{-1}(f_{2})fof the point 2, and the values there can only be 2 or 3. We therefore need only to evaluate a transversal_{2}^{-1}(2)TofThe desired transversalG_{f2}\\{2,3}^{f2-1(2)}.Tthen consists of the mappings_{3}fsuch that_{3}"Î3^{n}f_{3}" |_{f2-1(2)}ÎT, and f_{3}" |_{n\f2-1(2)}=f_{2}|_{n\f2-1(2)}.

consisting of the biggest elements of the orbits does exist. Moreover, we can break this problem into pieces, if weights are at hand.T_{>}(G\\Y^{X}),

It is important to note that we had to check 24 sequences for canonicity, out ofExample:Recall that the graphs onvvertices correspond to the set of orbitsAsS_{v}\\2^{v choose 2}.is totally ordered, so is the set of pairsv, and hence also the set of labelled graphs. This is in fact the lexicographic ordervchoose 2£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 isnota 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:Now we will evaluateT_{>}^{(0)}={(0,0,0,0,0,0)}.T, then_{>}^{(1)}T, and so on, in the following way. Assume that_{>}^{(2)}Tis at hand. Then, in order to obtain_{>}^{(i)}T, we shall apply to each member of_{>}^{(i+1)}Tthe following_{>}^{(i)}augmentation. We change in each element ofTin all the possible ways just one entry zero that is_{>}^{(i)}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 transversalT. In our example this process runs as follows:_{>}^{(i+1)}

- [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, clearlyT_{>}^{(1)}={(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, thatT_{>}^{(2)}={ (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 ofTneeds not to be considered, as there is no zero entry to the right of the rightmost entry 1. Thus_{>}^{(2)}T_{>}^{(3)}={(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 ofT, nothing new from the second one, but_{>}^{(3)}(1,1,0,0,1,1)from the third element, and henceT_{>}^{(4)}={(1,1,1,1,0,0),(1,1,0,0,1,1)}.- [5.] The next step gives
from which we obtain inT_{>}^{(5)}={(1,1,1,1,1,0)},- [6.] the final step that
And so, summing up, we have obtained the desired canonic transversal of the isomorphism classes of labelled graphs on 4 vertices:T_{>}^{(6)}={(1,1,1,1,1,1)}.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 actionwhere_{G}XXis totally ordered by£and a disjoint unionof invariant and nonempty subsetsX=È^{n}_{i=1}X_{i},X. Let_{i}Adenote an algorithm that produces for eachxÎXeither the empty set or a setA(x)ÍXin descending order, such that the following conditions hold for the canonic transversalsTof the orbit sets_{>}^{(i)}G\\X, for each_{i}iÎ:n-1Then, computing

T, union over the_{>}^{(i+1)}ÍÈA(x)xÎT,_{>}^{(i)}}- for each
xÎTthere exists a unique element_{>}^{(i+1)}x'ÎTsuch that_{>}^{(i)}xÎA(x'), and finally,- for any
x,_{1},x_{2}ÎT_{>}^{(i+1)}x, we have the implication_{1}<x_{2}x_{1}ÎA(x'_{1}),x_{2}ÎA(x'_{2}) imply x'_{1}<x'_{2}.Tand recursively running through_{>}^{(1)}Twith_{>}^{(i)}x, producing the augmentationA(x), and eliminating representatives which are not canonic fromA(x), foriÎ, gives the desired canonic transversaln-1Tof_{>}G\\Xas the following union:T_{>}=È_{i=1}^{n}T_{>}^{(i)}.

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*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.^{X}

**Exercises**

E:Check the lemma.

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001

Recursion and orderly generation |