Während der letzten zwei Jahre wurden im Rahmen des Forschungsprojekts Konstruktion endlicher Strukturen interessante Resultate in den Themenkreisen Codierungstheorie, Isomerabzählung von Fullerenen, Mathematische Musiktheorie, Kombinatorische Species-Theorie und Konstruktion von Bahnenrepräsentanten erzielt, die auch in mehreren Publikationen (siehe Literaturverzeichnis [5] - [14]) dokumentiert wurden. Im Zuge der Darstellung der erzielten Ergebnisse wollen wir zusätzlich einen Ausblick auf zukünftig geplante Forschungsvorhaben geben.

1. Codierungstheorie:

   Isometrieklassen linearer (n,k)-Codes über einem endlichen Körper können als Bahnen von k-dimensionalen linearen Unterräumen von GF(q)ⁿ unter der Aktion der vollen monomialen Gruppen GF(q)^* wr S_n aufgefaßt werden. (Siehe [19].) Nach genauer Analyse dieser Situation war es dann unter Verwendung des Lehmann'schen Lemmas [23][24] (das eine Methode angibt, die Aktion des Kranzproduktes in Form der Exponentiation durch einfachere Gruppenaktionen zu ersetzen) möglich, die Methoden von Slepian [31] für den Fall q=2 auf beliebiges q zu verallgemeinern, und unter Verwendung von Zyklenzeigern projektiver linearer Gruppen, operierend auf projektiven Räumen, die Anzahlen dieser Isometrieklassen zu bestimmen. In diesem Zusammenhang ist auch noch auf eine Formel zur Berechnung der Anzahl von Klassen unzerlegbarer linearer Codes hinzuweisen, die eine nicht näher angegebene oder bewiesene Formel von Slepian korrigiert und verallgemeinert. Dieser Forschungsschwerpunkt steht in enger Zusammenarbeit mit dem Lehrstuhl II für Mathematik unter der Leitung von Prof. A. Kerber [22], wo dann für den Fall q=2 vollständige Repräsentantensysteme für Isometrieklassen unzerlegbarer Codes für verschiedene Parameter k und n konstruiert wurden. In diesem Zusammenhang sind folgende zwei Publikationen [13] und [11] zu erwähnen. Überdies war es Herrn Fripertinger unter Verwendung von Reisemitteln, die durch den Fond zur Verfügung gestellt wurden, möglich, diese neuen Erkenntnisse im Rahmen der AAECC-11, die im Juli 1995 in Paris stattfand, vorzustellen. Einen weiteren Vortrag über Methoden der algebraischen Kombinatorik und deren Anwendungen zur Bestimmung der Anzahl der Isometrieklassen linearer Codes hielt Herr Fripertinger im Rahmen der Mathematikertagung Graz-Zagreb in Motovun.

   In einem gesonderten Artikel [6] werden von Herrn Fripertinger die Details über die Berechnung der Zyklenzeiger linearer, affiner und projektiver Gruppen dargestellt. Dieser Artikel wurde vom Journal of Linear Algebra and Its Applications als Publikation angenommen und wird derzeit gerade gedruckt.

   Allgemeiner wurden dann auch Isometrieklassen von [n,m] Block-Codes über einem endlichen Alphabet A untersucht. Diese lassen sich als S_A wr S_n-Bahnen von k-Teilmengen von Aⁿ auffassen. Damit ist es dann möglich, die Anzahlen von Isometrieklassen zu bestimmen, und unter Verwendung von Konstruktionsmethoden (Berechnung von Sims-Ketten [28][29], orderly generation kombiniert mit Read's Rekursionsmethode [1][26], Lerneffekte [15]) Transversalen für bestimmte Parametersätze (A,n,m) zu erzeugen. Da die Anzahl dieser Isometrieklassen aber sehr rasch steigt, und der Konstruktionsaufwand deshalb zu groß wird, ist es auch möglich mit Hilfe des Dixon-Wilf-Algorithmus [2] Repräsentanten über alle Isometrieklassen gleichverteilt, zufällig zu erzeugen. Im Fall A={0,1} entsprechen diese Isometrieklassen Klassen von Boolschen Funktionen bzw. Schaltfunktionen, die bereits von Slepian [30] und Harrison [17] untersucht wurden. Repräsentanten der Isometriklassen von Block-Codes können auch als Ausgangspunkt für die Konstruktion aller Repräsentanten von Post-Funktionen [18] verwendet werden. Diese Forschungsergebnisse konnten im Rahmen der Tagung Groups in Action 96, Thurnau, 20. bis 24. Oktober 1996 vorgeführt werden. Ein Artikel darüber [7] wird gerade fertiggestellt, um dann zur Publikation eingereicht zu werden.

   Oben beschriebene Methoden zur Abzählung (und Konstruktion) von Isometrieklassen linearer Codes lassen sich in den Fällen q=2,3 unmittelbar für die Klassifikation binärer und ternärer Matroide verwenden [33][34]. Im Rahmen der Tagung Groups in Action 96 konnte persönlicher Kontakt zu Prof. M. Wild geknüpft werden, mit dem eine Zusammenarbeit bei der Klassifikation regulärer Matroide vereinbart wurde. Dazu müssen die konstruierten Matroide (bzw. Repräsentanten der Isometriklassen binärer linearer Codes) einem Regularitätstest unterzogen werden, der jedoch erst einmal implementiert werden muß. Anschließend wollen wir versuchen eine Version des Dixon-Wilf-Algorithmus zu entwerfen, die in Verbindung mit diesem Regularitätstest reguläre Matroide zufällig erzeugt.

   Weiters soll im Rahmen des geplanten Forschungsvorhabens untersucht werden, ob es sinnvoll ist, und wie weit es möglich ist, die Konstruktionsverfahren von Isometriklassen binärer linearer Codes für beliebiges q zu verallgemeinern.

2. Isomere der Fullerene

   Wie in der ersten Projektbeschreibung für dieses Forschungsprojekt mehrfach erwähnt, stellt die Chemie ein wichtiges Gebiet zur Anwendung von Methoden der algebraischen Kombinatorik dar. In [12] wird der Zyklenzeiger der Symmetriegruppe des C₆₀-Moleküls bestimmt. (Das C₆₀-Molekül ist der bedeutendste Vertreter der Fullerene, die vor ca. 10 Jahren entdeckt wurden und eine sehr interessante neue Form von Kohlenstoffmolekülen darstellen.) Dieser Zyklenzeiger kann zur Bestimmung der Anzahl aller verschiedener Isomere zum Beispiel der Form C₆₀H_kCl_60-k oder zur Berechnung aller Hetero-Fullerene verwendet werden. Mit einer konstruktiven Methode werden alle 12500 möglichen Resonanzstrukturen von C₆₀ bestimmt und daraus unter Verwendung eines Bahnenalgorithmus alle 158 wesentlich verschiedenen Resonanzstrukturen und deren Symmetriegruppen bestimmt. Darüberhinaus wird eine mehr-dimensionale Version des Zyklenzeigers angegeben und die genaue Implementierung dieser Methoden in SYMMETRICA [32] beschrieben. Abschließend werden noch die Zyklenzeiger verschiedener anderer Fullerene C₂₀ bis C₁₄₀ angegeben. Dieser Artikel erschien im 33. Band der Zeitschrift MATCH, welcher den Fullerenen gewidmet ist. Mit den darin vorgestellten Methoden ist es den Chemikern möglich, auf theoretische Weise Obergrenzen für die Anzahl von Isomeren zu bestimmen.

   Unter Verwendung der Leapfrog Methode [4][3] konstruiert Fowler unendliche Folgen von Fullerenen C_n -> C_3n -> C_9n -> ... mit gleichen Symmetrieeigenschaften. Diese Methode kann auf beliebige Polyeder angewendet werden. In [5] wird eine Methode angegeben, die es erlaubt, aus den 3-dimensionalen Zyklenzeigern für die Aktionen der vollen Symmetriegruppe bzw. der Gruppe aller echten Rotationssymmetrien auf Ecken, Kanten und Flächen eines Polyeders P, die entsprechenden 3-dimensionalen Zyklenzeiger für den Leapfrog L(P) zu bestimmen. Diese Arbeit wurde zur Publikation eingereicht.

   Auf der 38. Tagung des Séminaire Lotharingien de Combinatoire in Bellagio hielt Herr Fripertinger einen Vortrag über diese Anwendungen in der Chemie der Fullerene.

3. Anwendungen in der Musiktheorie

   Nach eingehenden Diskussionen via e-mail mit Prof. R. Morris von der Eastman School of Music und mit B. Alegant entstand der Artikel [8]. Mosaics sind Orbits von Partitionen unter gewissen Gruppenaktionen, die musiktheoretisch begründet werden können. Unter Verwendung kombinatorischer Methoden aus dem Gebiet der Pólya-Theorie werden die Gesamtanzahl von Mosaics und die Anzahl von Mosaics zu gegebenem Stabilisatortyp bestimmt. Weiters werden Methoden angegeben, die zur Bestimmung der Anzahl von Orbits von Partitionen zu gegebenem Block-Typ verwendet werden können. Dieser Artikel wurde bei den Elementen der Mathematik zur Publikation eingereicht. Einige dieser Anzahlen von Mosaics waren bereits auf empirische Weise gefunden worden, nun kann man in beliebiger n-Ton-Musik Anzahlen von Mosaics berechnen.

   Am 24. Mai 1996 war Herr Fripertinger eingeladen, an dem Institut für Mathematik der Universität Innsbruck einen Vortrag über Anwendungen der Methoden der Algebraischen Kombinatorik auf dem Gebiet der Musiktheorie [9] zu halten.

   Kürzlich nahm Prof. G. Mazzola wieder Kontakt mit Herrn Fripertinger auf. Er interessiert sich für gewisse Verallgemeinerungen von Konstruktionsverfahren für Motive [25] in Z_n´Z_m, die Herr Fripertinger in seiner Dissertation [10] für den Fall von Motiven in Z₁₂´Z₁₂ entwickelte. In diesem Zusammenhang wollen wir Orbitrepräsentanten von k-Teilmengen von Z_n´Z_m unter der Aktion der Gruppe aller affinen Abbildungen auf Z_n´Z_m konstruieren.

4. Endofunktionen von gegebenem Zykeltyp

   In Zusammenarbeit mit P. Schöpf, einem Institutsmitglied, entstand der Artikel [14]. Am Anfang dieser Arbeit stand dessen Vorlesung über Mathematik und Literatur, in der auch S. Becketts Roman "Watt" vorkam. Dieser beschreibt eine Situation, in der fünf Leute versuchen, sich gleichzeitg, ohne vorherige Absprache, in Paaren gegenseitig in die Augen zu schauen, aber kläglich daran scheitern. Daraus erhebt sich die Frage, in wievielen Situationen wenigstens zwei Leute sich gegeseitig in die Augen sehen. Eine mathematische Formulierung dieser Situation führt zu den sogenannten Endofunktionen. Durch Iteration von Endofunktionen entsteht eine Zykelstruktur. In der vorliegenden Arbeit werden Anzahlen von (Orbits von) Endofunktionen mit vorgegebenen Zykeleigenschaften berechnet. Insbesondere erhält man damit eine nicht-rekursive Formel für die Anzahl aller (Orbits von) Wurzelbäumen. Diese Arbeit wurde zur Publikation eingereicht. Überdies hielt Herr Fripertinger im Rahmen der 34. Tagung des Séminaire Lotharingien de Combinatoire einen Vortrag zu diesem Thema.

5. Kombinatorische Species-Theorie

   Die kombinatorische Species-Theorie wurde von Joyal mit [20] begründet. Zu jeder Species gibt es drei formale Potenzreihen, die Zykelindexreihe, die Kardinalitätenreihe und die Typenreihe. Die erste enthält ähnliche Informationen wie ein Zyklenzeiger, die zweite ist eine exponentielle erzeugende Funktion für die Anzahlen einer Species, die dritte ist eine gewöhnliche erzeugende Funktion für die Anzahl aller Typen einer Species. Im Rahmen des Forschungsprojekts Konstruktion endlicher Strukturen wurden im Computeralgebrasystem SYMMETRICA oben erwähnte formale Potenzreihen für verschiedenste Species wie z.B. lineare Ordnungen, Permutationen, Endofunktionen, Wurzelbäume, Partitionen usw. implementiert. Mittels Verknüpfungen wie z.B. Summe, Produkt, Substitution, Ableitung, Punktierung usw. kann man aus gegebenen Species neue Formen von Species erzeugen. Diese Verknüpfungen wurden auf der Ebene der Potenzreihen ebenfalls programmiert. In SYMMETRICA gibt es einen Objekttyp Reihe, der ermöglicht, Anfangsstücke von Potenzreihen zu bestimmen, und das Bildungsgesetz dieser Reihen so zu verwalten, daß es jederzeit möglich ist, eine vorliegende Reihe zu erweitern.

   Nun wäre es interessant sich von dem rein abzählenden Standpunkt zu lösen, und konstruktive Species-Theorie zu betreiben. Das hieße, daß man sich mit Hilfe eines solchen Programmes alle Objekte einer Species auf gegebener Grundmenge, oder vollständige Repräsentantensysteme der Typen solcher Species konstruieren könnte. In diesem Zusammenhang müßten dann auch oben angegebene Operationen auf Species auf konstruierte Species anwendbar sein.

6. Gruppenaktionen auf Y^X

   Gruppenaktionen auf der Menge aller Funktionen von X nach Y induziert durch Gruppenaktionen auf X oder Y gehören zu den Standardmodellen der hier behandelten Theorie [21]. Viele diskrete Strukturen lassen sich auf diese Weise darstellen. Die Abzählformeln in diesen Situationen sind vollständig untersucht. Dies gilt jedoch nicht für das Gebiet der Konstruktion von Bahnentransversalen. Die Methoden zur Konstruktion unter Gruppenaktionen, die nur auf dem Definitionsbereich X operieren, sind bereits sehr leistungsfähig, sodaß man z.B. bereits alle Graphen mit 12 Knoten auflisten kann [16]. Die anderen Gruppenaktionen jedoch sind noch nicht systematisch untersucht worden. Insbesondere zeigte Herr Fripertinger auf, welche Bedeutung dem Lehmann'schen Lemma auf dem Gebiet der Konstruktionen zukommt, oder wie man das Homomorphieprinzip [21] bei Gruppenaktionen, die nur auf dem Bildbereich operieren, einsetzen kann, und dadurch zu einem rekursiven Verfahren über die Mächtigkeit von X gelangt. Weitere systematische Analyse der Möglichkeiten, vollständige Listen von Orbitrepäsentanten zu erzeugen, sollte betrieben werden. Die daraus hervorgehenden Algorithmen sollten zu einem Programmpaket in SYMMETRICA ausgebaut werden.

7. Implementierung kombinatorischer Algorithmen in SYMMETRICA

   SYMMETRICA ist ein Computeralgebrasystem, das die Gebiete Darstellungstheorie, Invariantentheorie und Kombinatorik symmetrischer Gruppen und verwandter Klassen von Gruppen abdeckt, welches am Lehrstuhl II für Mathematik der Universität Bayreuth entwickelt wird. Von Herrn Fripertinger wurde ein Großteil der Routinen verfaßt, die zu dem weiten Gebiet der Pólya-Theorie gezählt werden können. So ist es jetzt möglich, Zyklenzeiger von Summen, Produkten, plethystischen Substitutionen oder der Exponentiation mit SYMMETRICA zu berechnen. Die Redfield'schen Operatoren [27] sind auf Zyklenzeiger anwendbar. Weiters gibt es aufwendige Routinen zur Berechnung der Zyklenzeiger für die natürlichen Operationen der linearen, affinen und projektiven Gruppen. Diese wurden zur Abzählung der Isometrieklassen linearer Codes verwendet. Wie bereits oben beschrieben, kann man die Zyklenzeiger verschiedenster Fullerene bestimmen und abzählende Species-Theorie betreiben. Diese Programme gehören weiter gewartet; Ergänzungen sollten auf dem Gebiet der Species-Theorie und der Konstruktionsverfahren erfolgen.

Ein Großteil der oben beschriebenen Forschungsschwerpunkte ist auch in Hypertext dokumentiert, sodaß dem Leser oft zusätzlich noch ermöglicht wird, die angegebenen Formeln gleich auf konkrete Probleme anzuwenden. Herr Fripertinger schrieb dazu einige SYMMETRICA Programme, die von den entsprechenden Hypertext-Seiten aus aktiviert werden können. Diese WWW-Seiten findet man unter der Adresse:

Die Verschiedenheit der hier in diesem Bericht dargestellten Probleme unterstreicht einmal mehr die allgemeine, universale Verwendungsfähigkeit der entwickelten Methoden zur Klassifikation und Konstruktion endlicher Strukturen unter einer gegebene Operation einer Gruppe. Da sich das Projekt derzeit in einem sehr interessanten und erfolgversprechenden Stadium befindet, hoffe ich, um einen ungestörten Fortgang der Forschungsarbeit gewährleisten zu können, auf baldige Begutachtung dieses Antrags.