| | | Obtained results |
During the last thirty months interesting results were found in coding theory, isomer enumeration of fullerenes, mathematical music theory, combinatorial species theory and construction of orbit representatives under group actions. Many of them are already published or will appear soon. Let me draw your attention to some of the main results:
Isometry classes of linear (n,k)-codes over GF(q) can be
described as orbits
of k-dimensional linear subspaces of GF(q)n under the action of the
full monomial groups GF(q)* wr Sn (cf. [31]).
Applying Lehmann's Lemma
[38][39]
(which describes a method to replace the action of a wreath product in form
of the exponentiation by simpler group actions) we succeeded in generalizing
methods of D. Slepian ([49] for q=2) to arbitrary prime-powers
q. Computing cycle indices for the action of projective linear groups
PGLk(q) on projective spaces PGk-1(q) we enumerated the isometry classes of
linear (n,k)-codes over GF(q) for many parameter triples (n,k,q).
Especially so called irreducible codes (each code can be described
as a sum of these codes) play an important role for a systematic
classification of linear codes. We deduced a formula for computing the
numbers of isometry classes of irreducible linear codes, which corrects and
generalizes a formula of Slepian. This research work was done in close
cooperation with prof. A. Kerber from the university of Bayreuth.
Here in Graz we developed algorithms for enumeration and random generation of
isometry classes of linear codes (cf. [23] and [19]).
In Bayreuth methods for computing complete catalogues of codes were
developed. These results on coding theory were presented at the
AAECC-11, July 1995, Paris and at the Mathematikertagung Graz-Zagreb
in Motovun.
For many parameter values n, k and q the numbers of isometry classes of
linear codes (with additional properties as "no repeated columns", "no
zero-columns" or "indecomposability") have been computed
[2][37] and in many cases there
are complete lists of representatives of these isometry classes available
[6].
See for instance
/home/home_codes.html.
All these new results will be published in a forthcoming book [7]
together with Kerber and other co-authors of Bayreuth and of
Hamburg-Harburg. This book will
probably be the first text-book on coding theory describing how to get
a complete overview over the isometry classes of linear codes. In other
words in one part of this book
we will describe all the details needed for enumerating these classes
(combinatorics under finite group actions, Pólya theory, cycle index
methods, especially the cycle indices of projective groups, ...)
and for constructing complete lists of these codes (Sims chains,
orderly generation combined with learning techniques, canonical forms,
...). Other parts of the book will give an introduction to error correcting codes
and describe interesting connections between representation theory of
groups and coding theory.
In addition to this our software developed for the
classification of linear codes will be made available by ftp.
In another paper [21] all details on the computation of cycle indices for the natural actions of linear, affine and projective groups were presented.
Furthermore we tried to classify with similar methods the isometry classes of [n,m] block codes over finite alphabets A. After describing these classes as SA wr Sn-orbits of k-subsets of An, we can again apply all methods described above for enumeration, construction and random generation of block-codes (cf. [15]). For A={ 0,1} these isometry classes are classes of Boolean functions or of switching functions, (cf. [48] and [29]). Furthermore applying the homomorphism principle ([34]) representatives of the isometry classes of block codes can be used as a "starting point" for the construction of representatives of Post-functions ([30]). These results were also presented at the meeting Groups in Action 96, Thurnau, October 1996.
Matroids, well known combinatorial objects, which are representable over a field F are called F-linear. We are especially interested in binary matroids (these are GF(2)-linear matroids) and in regular matroids, which are representable over any field F. According to the so called Brylawski-Lucas-Theorem [8] the same methods and results concerning enumeration, construction and random generation of linear codes can be used for classifying GF(q)-linear matroids for q=2,3. There are many interesting characterizations of regular matroids [1] and together with M. Wild [51][52] we designed and implemented a regularity test for binary matrix matroids in the computer algebra system SYMMETRICA [50]. This test takes as an input a binary matrix matroid and decides whether this matroid is regular or not. Since we have complete lists of the isomorphism classes of binary matrices we can produce complete lists of regular matrix matroids. This test seems to be the first regularity test for matroids which is completely implemented in a computer algebra system. When applying this regularity test on a matrix matroid we get some further information about it. For instance the sets of all hyperplanes, co-lines and co-planes are computed or we can get an overview over all flats (closed sets) of a matroid. These ideas were presented at the 39-th Séminaire Lotharingien de Combinatoire, Thurnau, April 1997.
Problems from chemistry were one of the main roots for developing algebraic combinatorics. In [20] it is described how to compute the cycle index of the symmetry group of the C60-molecule. (C60 is the most important member of the family of fullerenes -- a very interesting new form of carbon-molecules --, which were detected a few years ago [36].) Using this cycle index for instance the numbers of different isomers of C60HkCl60-k molecules or of so called hetero fullerenes can be computed. Using the methods for computing orbit representatives we detected that all 12500 resonance structures of C60 belong to 158 orbits of resonance structures which were finally classified according to their stabilizer type. Furthermore multidimensional cycle indices for the simultaneous action on the sets of vertices, faces and edges of fullerenes were computed for various fullerenes from C20 to C140. And their implementation in SYMMETRICA is described.
Applying the Leapfrog method [14][13] P.W. Fowler computes infinite series of fullerenes of the form Cn -> C3n -> C9n -> ... the members of which all have the same symmetry groups. This method can be applied to any polyhedron. In [22] we describe a method how to compute from the 3-dimensional cycle index for the action of the full symmetry group and of the group of all rotational symmetries on vertices, edges and faces of a polyhedron P the 3-dimensional cycle index for these actions on the leapfrog L(P). These results were also presented at the 38-th meeting of the Séminaire Lotharingien de Combinatoire in Bellagio, October 1996.
Some discussions together with prof. R. Morris from Eastman School of Music and with B. Alegant lead to some new applications of our combinatorial methods to music theory (cf. [16]). Mosaics are orbits of partitions under certain group actions which can be motivated by music theory. We developed methods for enumerating all mosaics, mosaics of given block-type and mosaics of given stabilizer-type. So far some of these numbers could be detected by empiric investigations, now you can enumerate mosaics in n-tome music for an arbitrary integer n.
On May 24, 1996 Dr. Fripertinger was invited to give a talk on applications of algebraic combinatorics in music theory [17] at the university of Innsbruck.
There are some further cooperations with prof. G. Mazzola, ETH Zürich, generalizing the methods for construction of orbit representatives of motives in Z12´Z12 (cf. [40]) given in [18] to constructions in Zn´Zm for arbitrary n and m.
The starting point for these investigations [24] was a mathematical problem from S. Beckett's novel "Watt". A mathematical reformulation of this problem leads to the following problem: Iteration of an endofunction (a function with the same (finite) set S as domain and range) induces a some sort of cycle structure on S. We determine the number of orbits of endofunctions with prescribed cycle structure. Especially we get a non-recursive formula for the number of orbits of rooted trees. These results were presented at the 34-th Séminaire Lotharingien de Combinatoire, Saint-Nabor, March 1995.
During the last 15 years the theory of combinatorial species (cf. [32]) was mainly developed in Montreal, Canada. It is dealing both with labelled and unlabelled structures, especially it allows to compute generating function for the numbers of various labelled and unlabelled structures. So far there is only one complete monograph [4][5] on species theory. It has a more or less complete bibliography on species theory. In addition to this one can find an introduction to species theory in [34]. Each species in combinatorial species-theory is associated with three formal power-series. These are the cycle index series, the cardinality series and the type counting series. The first of them contains information similar to a cycle index, the second is an exponential generating function for numbers of elements of a species, the third is an ordinary generating function for numbers of types of a species. These generating functions were implemented in the computer algebra system SYMMETRICA for various standard species like for instance for linear orders, permutations, endofunctions, rooted trees, partitions. Furthermore there exist certain operations on species e. g. sum, product, substitution, punctuation which can be used for constructing new species from given species. For instance endofunctions can be considered as permutations of rooted trees. These operations correspond to operations on generating functions, which were implemented in SYMMETRICA as well. There exists a data-type Reihe in SYMMETRICA which allows to compute the first summands of a generating function. The next summands in such an formal power series can always be computed since this data-type holds all the information for computing further summands.
SYMMETRICA is a computer algebra system mainly developed at the Lehrstuhl II for mathematics at the university Bayreuth. It can be used to solve problems from representation theory, invariant theory and combinatorics of symmetric groups and of related classes of groups. Most of the routines dealing with enumeration under group action were developed by Fripertinger. It is possible to compute cycle indices of sums, products, plethysm or exponentiation of cycle indices. Die Redfield Ç and È-operators (cf. [45]) are implemented. Furthermore formulae for computing cycle indices of natural actions of linear, affine and projective groups are at hand, which were used for the enumeration of isometry classes of linear codes. Cycle index formulae for various fullerenes are available. Further programs for enumerative species theory and orbit representative construction were written.
Most of this research work was documented in articles or books, some parts are available by hypertext as well. Using these hypertext pages it is possible to apply the described algorithms to your own problems since there exist some SYMMETRICA programs which can be started from these pages. See:
http://bedvgm.kfunigraz.ac.at:8001/frib/index.html.
With this report we tried to prove how flexible these methods from algebraic combinatorics can be applied to very different problems in classification of discrete structures under given group actions.
As was already described very interesting research work was done and will be done in cooperation with prof. A. Kerber from Lehrstuhl II of the university in Bayreuth. He himself hopes to continue and intensify this collaboration during the next years. In the field of matroid theory we are planning to work together with prof. M. Wild, Stellenbosch University, South-Africa. Furthermore there will be some cooperation with G. Mazzola, ETH Zürich, in the field of mathematical music theory.
Based on the results of this research project we started a new research project Combinatorial construction under group actions P12642-MAT which should lead to some further results concerning codes and matroids and to an implementation of constructive species theory.
| | | Obtained results |