Vorlesung Symmetrische Gruppen

Wintersemester 2007/08

Prof. Dr. S. König
Dr. R. Hartmann
Mathematisches Institut der Universität zu Köln

Vorlesung

Mittwochs 8:15-9:45 im Hörsaal des Mathematischen Instituts.

Die Vorlesung Symmetrische Gruppen soll Vertrautheit mit diesen Gruppen und einigen ihrer vielfältigen Anwendungen herstellen. Besondere Vorkenntnisse werden nicht vorausgesetzt, es werden aber gelegentlich Ergebnisse aus anderen Vorlesungen verwendet. Nach einer Einführung in gruppentheoretische Grundlagen sollen vor allem kombinatorische Aspekte besprochen werden. Bei den Anwendungen sollen vor allem Alltagssituationen modelliert und erklärt werden wie das Mischen von Spielkarten, Kartentricks, Rätselaufgaben, Wartschlangen beim Einsteigen in ein Flugzeug und Ähnliches. Dabei werden auch grundlegende Algorithmen vorgestellt. Die einzelnen Kapitel der Vorlesung sind weitgehend voneinander unabhängig.

Kapitel 1: Mathematisches Modell des Kartenmischens.
Oktober 17, 24, 31, November 7.
In- und Out-Shuffle und Abheben als Permutationen, ihre Ordnungen bei gerader oder ungerader Kartenzahl, die von Out-Shuffle und Abheben erzeugten Untergruppen (Satz von Golomb), Erklärung eines Kartentricks.
Literatur: Morris, insbesondere das Kapitel 'A poker challenge deal'. Diaconis für weitergehende statistische Untersuchungen des Kartenmischens.

Kapitel 2: Permutationen, Youngdiagramme, Tableaux und Flugzeugpassagiere.
November 7, 14, 21, 28.
Kombinatorische Objekte: Partitionen, Youngdiagramme, Tableaux, Standard-Tableaux. Der Robinson-Schensted-Knuth-Algorithmus. Aufsteigende Teilfolgen. Viennots Schattendiagramme. Warteschlange mit Flugzeugpassagieren: Erwartungswert der Wartezeit.
Literatur: Stanley, Bona, Sagan, Fulton, jeweils die Abschnitte über den RSK-Algorithmus und über aufsteigende Teilfolgen.

Kapitel 3: Kombinatorische Verteilungen.
November 28, Dezember 5, 12, 19, Januar 9.
Zählen von Permutationen und anderen kombinatorischen Objekten; Rekursionsformeln, erzeugende Funktionen, Argumente aus der elementaren Wahrscheinlichkeitstheorie. Permutationen mit vorgegebener Zykelstruktur. Permutationen mit vorgegebener Zyklelzahl (vorzeichenlose Stirlingzahlen erster Ordnung). Descent-Menge, Eulersche Polynome und Eulersche Zahlen. Wahrscheinlichkeiten bei der Platzierung von Werten in Zyklen. Die Hakenformel (stochastischer Beweis). Erwartungswert der Länge aufsteigender Teilfolgen (Vershik-Kerov und Logan-Shepp): heuristisches Argument mit Variationsrechnung.
Literatur: Stanley 1.3, Beweis der Hakenformel: Bona.

Kapitel 4: Aufsteigende Teilfolgen, statistische Verteilungen und Analysis.
Januar 9, 16, 23.
Patience-Sortieren, gierige Strategie ist optimal. Zufallsvariable, Verteilungsfunktion, Binomialverteilung, Poissonverteilung, stochastische Prozesse, Poissonprozesse, Tracy-Widom-Verteilung. Der Satz von Baik, Deift und Johansson: Die Länge aufsteigender Teilfolgen ist Tracy-Widom-verteilt. Beispiele von Tracy-Widom-Verteilungen: Eigenwerte von Zufallsmatrizen, Teilchenstreuung, Busse der Linie 4 in Cuernavaca, Nullstellen der Riemannschen Zetafunktion.
Literatur: ICM 2006 (Artikel von Deift und von Stanley).

Kapitel 5: Die Partitionenfunktion p(n) in der Zahlentheorie.
Januar 23, 30.
Die Hardy-Ramananujan-Rademacher Formel für p(n). Beziehung zu Gittern, elliptischen Kurven und Modulfunktionen. Ramanujans Kongruenzen.
Literatur: G.Andrews, Theory of Partitions. M.Knopp, Modular functions in analytic number theory.

Kapitel 6: Knoten und Zöpfe.
Januar 30, Februar 6.
Äquivalenz von Knoten, Reidemeisterbewegungen. Die Artinsche Zopfgruppe und Markov-Äquivalenz. Das Jones-Polynom. Ocneanu-Spur, Heckealgebra, Temperley-Lieb-Algebra und quantisierte Einhüllende von sl(2,C).
Literatur: L.Kauffman, Knots and Physics. V.Chari and A.Pressley, A guide to quantum groups.

Glossar

Übungsblätter:

Blatt 1
Blatt 2
Blatt 3
Blatt 4
Blatt 5

Literatur:

Richard Stanley, Enumerative combinatorics, vol. 1, vol. 2 (hervorragendes Standardwerk, auch als spannende Lektüre für lange Ferien geeignet)
Miklos Bona, Combinatorics of permutations
Bruce Sagan, The symmetric group
Gordon James and Adalbert Kerber, The representation theory of the symmetric group
Adalbert Kerber, Applied finite group actions
William Fulton, Young tableaux
Persi Diaconis, Group representations in probability and statistics
Brent Morris, Magic tricks, card shuffling and dynamic computer memories

Kontakt und Sprechzeiten

Prof. Dr. S. Koenig
Sprechzeiten Donnerstags 10.30-11.30 Uhr und nach Vereinbarung
Zimmer 106 im Mathematischen Institut
Telefon 0221-470-3431
email skoenig(at)math.uni-koeln.de

Dr. R. Hartmann
Sprechzeiten Mittwochs 10-11 und Donnerstags 13-14 Uhr, andere Zeiten nach Vereinbarung
Zimmer 111b im Mathematischen Institut
Telefon 0221-470-3713
email rhartman(at)math.uni-koeln.de