Obtained resultsTopPreliminaries

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 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

Obtained resultsTopPreliminaries