Vorlesung (BaM-DAM-k, MaM-DASA-k)

Geometrische und algebraische Methoden
in der Kombinatorik

Winter Semester 2016/17

Prof. Raman Sanyal

Aktuelles

Es gibt ein Bonussystem! Siehe unten.
Räume und Zeiten haben sich geändert!
Vorlesung geht am 18.10. los.

Was

Laut dem Duden ist die Kombinatorik ein "Teilgebiet der Mathematik, dass sich mit den möglichen Kombinationen gegebener Dinge (Elemente) befasst". Diese nüchterne Beschreibung tut der hohen Kunst des Zählens unrecht. In dieser Vorlesung wollen wir Dinge auf besonders elegante Art und Weise mit Hilfe von Geometrie und Algebra zählen. In 10-12 ausgewählten Kapiteln beschäftigen wir uns unter anderem mit

Wälder in Graphen und Gitterpunkte in Zonotopen
Permutationen, Euler-Zahlen, und Volumina
Partitionen, Rekurrenzen und Ringe formaler Potenzreihen
Prinzip von Inklusion-Exclusion, Inzidenz- und Möbius-Algebren
Binäre Bäume, Triangulierungen und Sekundärpolytope
Orientierungen, Arrangements von Hyperebenen und Charakteristische Polynome
Graphenfärbungen, quasi-symmetrische Funktionen und Hopf-Algebren

Voraussetzungen dafür sind diskrete Mathematik (BaM-DM) sowie lineare Algebra (BaM-LA1, BaM-LA2). Weiteres Wissen in (diskreter) Geometrie und (kommutativer) Algebra sind hilfreich aber nicht zwingend notwendig.

Link zum Vorlesungsverzeichnis.

Wann und wo

Vorlesung: Dienstags, 14-16, Neue Mensa NM130
Übung: Mittwochs, 14-15, Robert-Mayer-Str. 10, Raum 109c

Organisation / Spielregeln

Die Übungen finden jede Woche statt.
Informationen/Spielregeln zu den Übungsblättern stehen unten.
Ob die Abschlussprüfung müdlich oder schriftlich ist wird später bekannt gegeben.
Es wird kein geLaTeXtes Skript geben. Allerdings stelle ich meine handschriftlichen Notizen zur Verfügung. Ich weise aber darauf hin, dass die Notizen Fehler enthalten können und auch nicht notwendigerweise vollständig sind. Es zählt was in der Vorlesung und Übung besprochen wird.

Was bisher geschah

Für meine handschriftlichen Notizen auf das entsprechende Datum klicken. Username/Passwort gibt es auf Anfrage.

18. Oktober Was ist Kombinatorik mit Hilfe von Geometrie und Algebra?
Graphen, Adjazenzmatrizen, Kantenzüge, Multiplizitäten; Anzahl (geschlossener) Kantenzüge durch Potenzen der Adjazenzmatrix; Spur und Eigenwerte; Beispiel: vollständige Graphen. Quellen: [AC, Ch. 1]

25. Oktober Zählfunktionen mit geschlossener/expliziter Form; Beispiel Fibonacci Zahlen; rationale Zählfunktionen; lineare Rekurrenzen; Formale Potenzreihen und erzeugenden Funktionen; Operationen auf erzeugenden Funktionen; Beispiele. Quellen: [EC, Ch. 4], [CRT, Ch. 4]

1. November Inverse von formalen Potenzreihen; Hauptsatz zu Rationale Erzeugenden Funktionen; Beispiele: Kompositionen mit ungeraden Teilen oder Teilen grösser 1 werden durch Fibonacci Zahlen gezäl.. Quellen: [EC, Ch. 4], [CRT, Ch. 4]

8. November Hyperebenen und Halbräume; Polyeder und Polytope; Simplexe \(\triangle_d\), Inneres und Ränder; Würfel \(\Box_d\) und Randstruktur; Volumen und normalisiertes Volumen; Zerlegung von \(\Box_d\) in \(d!\) kongruente Kopien von \(\triangle_d\) mit Permutationen; Anwendung: Wie wählt man eine zufällige Permutation? Quellen: [CRT, Sec. 5.7]

15. November Punkte in \(\Box_d^\circ\) und surjektive Abbildungen \( f : [d] \twoheadrightarrow [k]\); diskretes Volumen, Ehrhart Funktionen von Wüfeln und Stirling-Zahlen der zweiten Art; Rationale erzeugenden Funktion von \(f(n) = n^d\); Ascents und Descents von Permutationen; Euler Zahlen; Worpitzskys Formel. Quellen: [CRT, Sec. 6 - sehr unvollständig]

22. November Halb-offene Zerlegungen; Abstiege (descents) in Permutationen und halb-offenen Simplexe; Beweis der Worpitzsky Formel; Halb-Ordnung und Beispiele; Existenz und Anzahl linearer Erweiterungen. Quellen: [CRT, Sec. 6 - sehr unvollständig]

29. November (strike) ordnungserhaltene Abbildungen und (strike) Ordnungspolynome; Ordnungspolytope; Jordan-Hölder Mengen und Zerlegungen in Simplexe; lineare Erweiterungen und Abstiege (descents)

6. Dezember Prinzip von Inklusion-Exklusion; Beispiel: Permutationen ohne Fixpunkt; Funktionen auf boolschen Verbänden und Inklusion-Exklusion; Allgemeiner: Funktionen auf Halbordnungen; Inzidenzalgebra eines Posets; Invertierbare Elemente; Zeta- und Möbiusfunktionen. Quelle: [CRT, Sec. 2.4], [EC, Ch. 3]

13. Dezember keine Vorlesung

20. Dezember Euler-Zahlen und Hypersimplexe; Satz: Normalisiertes Volumen \(\Delta(d+1,k+1)\) is die Anzahl von Permutationen von \([d]\) mit \(k\) Abstiegen (descents); 1. Ansatz: Zerlegung von \(\Delta(d+1,k+1)\) in Pyramiden; Volumen berechnung gibt Rekursionsformel; 2. Ansatz: Hypersimplexe (wie auch Ordnungspolytope) sind alcoved Polytope. Quelle: [CRT, Sec. 7.4]

10. Januar Objekte zählen unter Symmetrie; Halsketten mit \(k\) schwarzen/weissen Perlen zählen bis auf Symmetrie; Linearisieren des Problems mit Hilfe von lin. Algebra; Tensorprodukte von Vektorräumen; Anzahl selbst-komplementärer Halsketten und die Spurformel auf Tensorprodukten

17. Januar Segmente, Minkowski Summen und Zonotope; das graphische Zonotop; Dimension und Zusammenhangskomponenten; Ecken und azyklische Orientierungen; Volumen und aufspannende Bäum. Quelle: [CRT, Sec. 7.5]

24. Januar chromatische Zahl, Cliquenzahl, perfekte Graphen; Stabilitätszahlen und Stabile-Mengen Polytope; Cliquen-Ungleichungen, Lovasz geometrische Charakterisierung von perfekten Graphen; Vergleichbarkeitsgraphen sind perfekt; Mirsky's Theorem; Chain-Polytope; Thm: Volumen von Chain- und Order-Polytopen sind gleich

31. Januar binäre Codes, Hamming Abstand; Obere Schranken an Grösse eines Codes mit gegebenem mindest Abstand; Delsarte Methode, Bose-Mesner Matrixalgebra. Quelle: [UULP, Sec. 8.4]

Übungsblätter

Übungsblätter sollen in Zweiergruppen bearbeitet und Dienstags vor Beginn der Vorlesung abgegeben werden. Jede Aufgabe wird binär mit `richtig' oder `falsch' bewertet. Das Übungsblatt gilt als bestanden, wenn Sie mindestens zwei Aufgaben richtig gelöst haben. Die mit einer schwarzen Box markierten Aufgaben dienen zur Vertiefung des Stoffs und sind prüfungsrelevant. Es gibt ein Bonussystem: Wenn (abgerundet) 75% der Übungsblätter erfolgreich bearbeitet wurden, dann wird die Note der bestandenen Abschlussprüfung um 0.3 verbessert (wenn dies möglich ist). Falls Sie Fragen zum Übungsblatt haben oder einen Fehler finden, dann schicken Sie mir doch einfach eine Mail.

1. Übungsblatt, Abgabe am 15. Oktober
2. Übungsblatt, Abgabe am 8. November
3. Übungsblatt, Abgabe am 22. November
4. Übungsblatt, Abgabe am 29. November
5. Übungsblatt, Abgabe am 6. Dezember
6. Übungsblatt, Abgabe am 20. Dezember
7. Übungsblatt, Abgabe am 10. Januar
8. Übungsblatt, Abgabe am 17. Januar
9. Übungsblatt, Abgabe am 24. Januar
10. Übungsblatt, Abgabe am 31. Januar

Literatur

[CRT]: Combinatorial Reciprocity Theorems. Matthias Beck, Raman Sanyal
[AC]: Algebraic Combinatorics: Walks, Trees, Tableaux, and More. Richard Stanley
[EC]: Enumerative Combinatorics, Volume 1. Richard Stanley
[UULP]: Understanding and Using Linear Programming. Jiri Matousek, Bernd Gärtner

18. Oktober	Was ist Kombinatorik mit Hilfe von Geometrie und Algebra? Graphen, Adjazenzmatrizen, Kantenzüge, Multiplizitäten; Anzahl (geschlossener) Kantenzüge durch Potenzen der Adjazenzmatrix; Spur und Eigenwerte; Beispiel: vollständige Graphen. Quellen: [AC, Ch. 1]
25. Oktober	Zählfunktionen mit geschlossener/expliziter Form; Beispiel Fibonacci Zahlen; rationale Zählfunktionen; lineare Rekurrenzen; Formale Potenzreihen und erzeugenden Funktionen; Operationen auf erzeugenden Funktionen; Beispiele. Quellen: [EC, Ch. 4], [CRT, Ch. 4]
1. November	Inverse von formalen Potenzreihen; Hauptsatz zu Rationale Erzeugenden Funktionen; Beispiele: Kompositionen mit ungeraden Teilen oder Teilen grösser 1 werden durch Fibonacci Zahlen gezäl.. Quellen: [EC, Ch. 4], [CRT, Ch. 4]
8. November	Hyperebenen und Halbräume; Polyeder und Polytope; Simplexe \(\triangle_d\), Inneres und Ränder; Würfel \(\Box_d\) und Randstruktur; Volumen und normalisiertes Volumen; Zerlegung von \(\Box_d\) in \(d!\) kongruente Kopien von \(\triangle_d\) mit Permutationen; Anwendung: Wie wählt man eine zufällige Permutation? Quellen: [CRT, Sec. 5.7]
15. November	Punkte in \(\Box_d^\circ\) und surjektive Abbildungen \( f : [d] \twoheadrightarrow [k]\); diskretes Volumen, Ehrhart Funktionen von Wüfeln und Stirling-Zahlen der zweiten Art; Rationale erzeugenden Funktion von \(f(n) = n^d\); Ascents und Descents von Permutationen; Euler Zahlen; Worpitzskys Formel. Quellen: [CRT, Sec. 6 - sehr unvollständig]
22. November	Halb-offene Zerlegungen; Abstiege (descents) in Permutationen und halb-offenen Simplexe; Beweis der Worpitzsky Formel; Halb-Ordnung und Beispiele; Existenz und Anzahl linearer Erweiterungen. Quellen: [CRT, Sec. 6 - sehr unvollständig]
29. November	(strike) ordnungserhaltene Abbildungen und (strike) Ordnungspolynome; Ordnungspolytope; Jordan-Hölder Mengen und Zerlegungen in Simplexe; lineare Erweiterungen und Abstiege (descents)
6. Dezember	Prinzip von Inklusion-Exklusion; Beispiel: Permutationen ohne Fixpunkt; Funktionen auf boolschen Verbänden und Inklusion-Exklusion; Allgemeiner: Funktionen auf Halbordnungen; Inzidenzalgebra eines Posets; Invertierbare Elemente; Zeta- und Möbiusfunktionen. Quelle: [CRT, Sec. 2.4], [EC, Ch. 3]
13. Dezember	keine Vorlesung
20. Dezember	Euler-Zahlen und Hypersimplexe; Satz: Normalisiertes Volumen \(\Delta(d+1,k+1)\) is die Anzahl von Permutationen von \([d]\) mit \(k\) Abstiegen (descents); 1. Ansatz: Zerlegung von \(\Delta(d+1,k+1)\) in Pyramiden; Volumen berechnung gibt Rekursionsformel; 2. Ansatz: Hypersimplexe (wie auch Ordnungspolytope) sind alcoved Polytope. Quelle: [CRT, Sec. 7.4]
10. Januar	Objekte zählen unter Symmetrie; Halsketten mit \(k\) schwarzen/weissen Perlen zählen bis auf Symmetrie; Linearisieren des Problems mit Hilfe von lin. Algebra; Tensorprodukte von Vektorräumen; Anzahl selbst-komplementärer Halsketten und die Spurformel auf Tensorprodukten
17. Januar	Segmente, Minkowski Summen und Zonotope; das graphische Zonotop; Dimension und Zusammenhangskomponenten; Ecken und azyklische Orientierungen; Volumen und aufspannende Bäum. Quelle: [CRT, Sec. 7.5]
24. Januar	chromatische Zahl, Cliquenzahl, perfekte Graphen; Stabilitätszahlen und Stabile-Mengen Polytope; Cliquen-Ungleichungen, Lovasz geometrische Charakterisierung von perfekten Graphen; Vergleichbarkeitsgraphen sind perfekt; Mirsky's Theorem; Chain-Polytope; Thm: Volumen von Chain- und Order-Polytopen sind gleich
31. Januar	binäre Codes, Hamming Abstand; Obere Schranken an Grösse eines Codes mit gegebenem mindest Abstand; Delsarte Methode, Bose-Mesner Matrixalgebra. Quelle: [UULP, Sec. 8.4]