The research program
A group action of a group G on a finite set X is given by a
mapping [32]
G´X -> X, (g,x) -> gx,
such that g1(g2x)=(g1g2)x and 1x=x for all xÎX and g1,g2ÎG. A group action defines several interesting structures, for instance
- an equivalence relation on X, given by
x~Gx'Û$gÎG:x'=gx,
- orbits G(x):={gx|gÎG)} which are the equivalence
classes of ~G,
- a partition G\\X:={G(x)|xÎX)} of the set X,
- the stabilizer Gx:={gÎG|gx=x)} of x, which is a
subgroup of G,
- the set Xg:={xÎX|gx=x)} of all fixed points of g.
In many cases discrete structures can be described as orbits under a
given group action. This means that in many cases we can apply the same
fundamental algebraic and combinatorial methods in order to classify,
catalogue, enumerate or construct discrete structures. (Some examples
how to apply these methods for finite graphs, linear codes, designs or
chemical structures can be found for instance in
[3][33][31]. Applications in the field of
musical theory can be found in [15].)
In a first step we
have to find a suitable definition of a structure as an orbit under a group
action. (For instance unlabelled structures are orbits of labelled ones.)
Then methods like the Cauchy-Frobenius Lemma, Burnside's Lemma,
Pólya-Redfield-de Bruijn Theory
[10][28][36][37][38][41]
can be applied for enumerating
these structures with given properties. The more details of a structure are
specified and prescribed by parameters the closer comes
the enumeration procedure
to the construction of all structures with given properties. The
most ambitious task is the computation of complete lists of representatives
of a discrete structure
[8][9][25][26][27][39][40][42].
Since computers get faster and cheaper, now it is
possible to reach regions with these construction methods one could not
imagine a few years ago. For example, the worldwide first 7- and
8-designs were recently constructed in Bayreuth.
When the numbers of representatives get too large in
order to compute complete lists, it is useful, helpful and makes sense to
compute representatives uniformly at random.
One of the main tasks planned for this project is to investigate the discrete
structures of (binary or regular) matrix matroids and of
linear codes.
Another main part should be concerned with labelled and unlabelled structures
in the framework of combinatorial species theory.
harald.fripertinger@kfunigraz.ac.at,
last changed: January 23, 2001
