Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

1999 | Book | 2. edition

Labeled Structures Read chapter Read first chapter

Applied Finite Group Actions

Author: Adalbert Kerber

Publisher: Springer Berlin Heidelberg

Book Series : Algorithms and Combinatorics

Included in: Professional Book Archive

Login to get access
insite
SEARCH

About this book

Also the present second edition of this book is an introduction to the theory of clas­ sification, enumeration, construction and generation of finite unlabeled structures in mathematics and sciences. Since the publication of the first edition in 1991 the constructive theory of un­ labeled finite structures has made remarkable progress. For example, the first- designs with moderate parameters were constructed, in Bayreuth, by the end of 1994 ([9]). The crucial steps were - the prescription of a suitable group of automorphisms, i. e. a stabilizer, and the corresponding use of Kramer-Mesner matrices, together with - an implementation of an improved version of the LLL-algorithm that allowed to find 0-1-solutions of a system of linear equations with the Kramer-Mesner matrix as its matrix of coefficients. of matrices of the The Kramer-Mesner matrices can be considered as submatrices form A" (see the chapter on group actions on posets, semigroups and lattices). They are associated with the action of the prescribed group G which is a permutation group on a set X of points induced on the power set of X. Hence the discovery of the first 7-designs with small parameters is due to an application of finite group actions. This method used by A. Betten, R. Laue, A. Wassermann and the present author is described in a section that was added to the manuscript of the first edi­ tion.

Table of Contents

Frontmatter
0. Labeled Structures
Abstract
Well-known discrete structures are graphs, linear codes, molecular graphs, designs. They usually occur in two forms, in a labeled form and in an unlabeled form. The difference between these forms is easily illustrated by graphs.
Adalbert Kerber
1. Unlabeled Structures
Abstract
The main aim of this book is an introduction to the theory of classification, enumeration, construction and generation of unlabeled structures which means equivalence classes of labeled structures. A typical example is formed by incidence structures, where the names of the points (the labels) do not really matter, and so two incidence structures that differ only by a renumbering of the points are considered as essentially the same, as equivalent or as isomorphic. Prominent examples are unlabeled graphs, isometry classes of linear codes, isomorphism classes of designs, equivalence classes of switching functions, physical states and chemical isomers. We shall discuss these cases in detail.
Adalbert Kerber
2. Enumeration of Unlabeled Structures
Abstract
We are now going to examine unlabeled structures. The first step is to compute their total number, for example, the number of graphs with prescribed number of vertices. Unlabeled structures will be described as orbits of groups on sets. For the purpose of their enumeration, the Cauchy-Frobenius Lemma is derived, it yields the number of orbits in the case when both the group and the set on which it acts are finite.
Adalbert Kerber
3. Enumeration by Weight
Abstract
Now we are going to refine our methods in order to enumerate orbits with prescribed properties. For this purpose we introduce weight functions on X, i. e. mappings from X into commutative rings which are constant on the orbits of G on X. The Cauchy-Frobenius Lemma will be refined in order to count orbits with prescribed weight. We shall use it, for example, in order to enumerate graphs with prescribed numbers of vertices and edges. This leads us to certain generating functions, the cycle indicator polynomials.
Adalbert Kerber
4. Enumeration by Stabilizer Class
Abstract
We now consider another refinement of the Cauchy-Frobenius Lemma. It is due to Burnside, and it allows to enumerate orbits which have a given conjugacy class of subgroups as stabilizers of their elements. For example, it allows us to count the orbits of maximal length |G|, the asymmetric orbits, since these are the orbits ω with trivial stabilizers G x = 1, for each x ∈ ω. A well known formula from Galois theory turns out to be such a number of asymmetric orbits.
Adalbert Kerber
5. Poset and Semigroup Actions
Abstract
We are now going to discuss finite actions G X,where X is a poset and where G respects the order: x < x′ ⇒ gx < gx′. Thus G acts as a group of automorphisms on (X, ≤). This yields generalizations of several notions introduced in the preceding chapter and it gives further insight. We shall also consider actions that respect the multiplication of a semigroup. Hence in particular lattice actions are considered as well as groups of automorphisms of partial orders, semigroups or other algebraic structures.
Adalbert Kerber
6. Representations
Abstract
It will turn out to be useful to refine the preceding considerations of permutation representations. We consider linear representations on corresponding vector spaces and decompose them into their irreducible constituents. Having done this we can use all what is known on ordinary irreducible representations of finite groups, in particular we can use the results on ordinary representation theory of symmetric groups which will give us further insight into the problems.
Adalbert Kerber
7. Further Applications
Abstract
We shall now refine our results on the enumeration of symmetry classes of mappings by using linear representations of finite groups, in particular of symmetric groups. Conversely, we shall apply to representation theory what we know about combinatorial enumeration. A first striking example is the theory of Schur polynomials. These symmetric polynomials will be defined here with the aid of irreducible characters of the symmetric group, and later on we shall show what these polynomials count. We shall discuss the diagram lattice, using representation theory first, and afterwards we can show its significance for unimodality questions about generating functions of enumeration theory.
Adalbert Kerber
8. Permutations
Abstract
We begin with a consideration of multiply transitive actions. Numbers will be derived that allow directly to see from the cycle structure of the group elements if the action is multiply transitive or not. Afterwards we shall enumerate permutations with prescribed algebraic and combinatorial properties. We consider roots in finite groups, which means that we take a fixed natural number k and ask for the number of group elements x, the k-th power of which is equal to a given element g of the group G, x k = g. The case when g = 1 is of particular interest. Then we restrict attention to the symmetric group, in order to derive expressions for the number of roots in terms of characters and to show how permutrizations can be applied. It will be shown that the function which maps a permutation onto the number of its k-th roots is in fact a proper character of the symmetric group in question.
Adalbert Kerber
9. Construction and Generation
Abstract
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 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 Y X with prescribed content λ. After that we describe a recur­sive method, using recursion on |Y|, and combining this recursion with the orderly generation method that was introduced by R. C. Read.
Adalbert Kerber
10. Tables
Abstract
This chapter contains tables of marks and Burnside matrices of the smallest cyclic, dihedral, symmetric and alternating groups. Moreover, the interested reader will find characters (reducible and irreducible) of symmetric groups, in order to support further applications by providing some numerical information. The irreducible char­acters are given, together with the Young characters and their decompositions. Also the scalar products of Young characters and products of Young characters and the al­ternating character are tabulated, since these numbers are numbers of 0–1-matrices with prescribed row and column sums. In addition the smallest Foulkes tables are shown since the characters occuring in enumeration theory of symmetry classes of mappings are linear combinations of Foulkes characters. Then the first 44 character polynomials are listed, each of them allows to evaluate an infinite series of ordinary irreducible characters of symmetric groups. The final section contains the 120 first Schubert polynomials.
Adalbert Kerber
11. Appendix
Abstract
In this appendix a few very basic or technical things are recalled in order to make the book selfcontained in a reasonable sense.
Adalbert Kerber
12. Comments and References
Abstract
This chapter begins with remarks on the history of finite group actions. The reader will then find comments that point to certain important articles and books, together with hints for further reading and additional references.
Adalbert Kerber
Backmatter
Metadata
Title
Applied Finite Group Actions
Author
Adalbert Kerber
Copyright Year
1999
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-662-11167-3
Print ISBN
978-3-642-08522-2
DOI
https://doi.org/10.1007/978-3-662-11167-3