<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 5 Issue 3" %>
Constructing Finite Unlabeled Structures Using Group Actions
Adalbert Kerber
Department of Mathematics, University of Bayreuth, 95440 Bayreuth, Germany
Annals of Combinatorics 5 (3) p.363-380 September, 2001
AMS Subject Classification: 05E25
The aim of this review is to point to a particular aspect of the constructive enumeration of finite unlabeled structures: The use of group actions and of double cosets in finite groups. In order to do this we start with a brief list of unlabeled structures, i.e., of mathematical structures defined as equivalence classes on finite sets. Then it will be shown that in each case the equivalence relation can be replaced by a finite group action, and so the whole bunch of tools of finite group actions' theory can be applied in each of these cases. The finite structures in question will be introduced as orbits of finite groups on finite sets, and so they can be obtained from transversals of orbit sets by simple deleting the labels. Therefore the construction of representatives of orbits, using double cosets, as well as the generation of representatives uniformly at random will be briefly described.
Keywords: combinatorics, unlabeled structures, enumeration under finite group action


1.  A. Betten, A. Kerber, A. Kohnert, R. Laue, and A. Wassermann, Es gibt 7-designs mit kleinen Parametern, Bayreuth. Math. Schr. 49 (1995) 2–13.

2.  A. Betten, A. Kerber, R. Laue, and A.Wassermann, Simple 8-designs with small parameters, Designs, Codes, Cryptography 15 (1998) 5–27.

3.  A. Betten, H. Fripertinger, A. Kerber, A.Wassermann, and K.-H. Zimmermann, Codierungstheorie, Konstruktion und Anwendung linearer Codes, 1999.

4.  H. Fripertinger, Enumeration of isometry classes of linear (n; k)-codes over GF(q) in SYMMETRICA, Bayreuth. Math. Schr. 49 (1995) 215–223.

5.  H. Fripertinger, Cycle indices of linear, affine and projective groups, Linear Algebra Appl. 263 (1997) 133–156.

6.  H. Fripertinger and A. Kerber, Isometry classes of indecomposable linear codes, In: Proc. of AAECC 11, Lecture Notes in Computer Science 948, Springer-Verlag, 1995, pp. 194–204.

7.  G.D. James and A. Kerber, The representation theory of the symmetric group, In: Encyclopedia of Mathematics and Its Applications, Addison Wesley, London, 1981.

8.  A. Kerber, Algebraic Combinatorics Via Finite Group Actions, BI-Wissenschaftsverlag, Mannheim, Wien, Zürich, 1991.

9.  A. Kerber, Applied Finite Group Actions, Springer-Verlag, 1999.

10.  A. Kerber and R. Laue, Group actions, double cosets, and homomorphisms: unifying concepts for the constructive theory of discrete structures. In: Acta Applicandae Mathematica, Sonderheft zur Kaloujnine-Gedächtnis-Tagung, 1994.

11.  A. Kerber, R. Laue, and T. Wieland, Discrete mathematics for combinatorial chemistry, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 51 (2000) 225–234.

12.  R. Laue, Construction of combinatorial objects—a tutorial, Bayreuth. Math. Schr. 43 (1993) 53–96.

13.  W. Lehmann, Das Abzähltheorem der Exponentialgruppe in gewichteter Form, Mitt. Math. Sem. Giessen 112 (1974) 19–33.

14.  W. Lehmann, Ein vereinheitlichender Ansatz für die REDFIELD – PÓLYA – de BRUIJNSCHE Abzähltheorie, Dissertation, Universität Giessen, 1976.