Constructions

# Constructions

We have counted the orbits of finite groups on finite sets and successively refined our methods by introducing enumeration by weight as well as enumeration by weight and stabilizer class. Moreover we discussed actions on structured sets like posets and semigroups. Later on the permutation group representations were refined by introducing linear representations, which led to applications in both directions. It remains to discuss the most difficult problem, the construction of a transversal of the orbits.

We shall briefly discuss the general case of this problem, in order to introduce the concept of Sims chains, for cases when the acting group is given by generators and relations. We shall then use it in a detailed description of a direct evaluation of a transversal of the orbits of G on YX with prescribed content l. After that we describe a recursive method, using recursion on | Y | , and combining this recursion with the orderly generation method that was introduced by R. C. Read.

These methods can be used for the evaluation of catalogues of discrete structures that can be defined as orbits of finite groups on finite sets, and in particular of discrete structures which can be considered as symmetry classes of mappings. For example, a catalogue of all the graphs on v£10 points was obtained in this way, as well as a catalogue of 0-1-matrices under the action of the direct product of the symmetric groups on the rows and columns (the contexts that are of interest for the concept analysis).

It is clear that for higher v it is nearly impossible to get such a catalogue of graphs, its cardinality is much too big. But nevertheless there are cases where one wants to try a hypothesis on graphs on 15 or 20 vertices, say. In these cases we can apply a recent and very important method of generating orbit representatives uniformly at random, which will also be described. It can be used, for example, in order to test graph invariants, and to do all kinds of examinations of structures that can be defined as orbits of finite actions by inspection of big sets of examples. It helps, say, easily to get nonisomorphic labelled graphs with same edge degree sequence and same characteristic polynomial, if we want to demonstrate that these two invariants are not complete, even if we put them together.

Finally we shall describe the corresponding problem in linear representation theory which is the evaluation of symmetry adapted bases. Such bases serve very well whenever there are symmetries.

• Orbit evaluation
• Transversals of symmetry classes
• Orbits of centralizers
• Recursion and orderly generation
• Generating orbit representatives