Preliminaries
The FWF-project P10189 - PHY Construction of finite structures was
mainly dealing with further investigations and applications of
classifications of finite structures using methods from algebraic
combinatorics, mainly combinatorics under finite group actions.
([34])
A group action of a group G on a finite set X is given by a
mapping
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][35][33]. Applications in the field of
musical theory can be found in [17].)
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
[11], [28], [39],
[41][42], [45]
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
[9][10][43][44],
[25][26], [27], [46][47].
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. (For any orbit
wÎG\\X the probability that a constructed representative
x lies in w is given by 1/ | G\\X | , i.e. it does not
depend on w.) The main idea for this construction
is known as the Dixon-Wilf-algorithm ([12]).
harald.fripertinger@kfunigraz.ac.at,
last changed: January 23, 2001
