In dieser ersten Vertiefungsveranstaltung geht es um grundlegende und
fortgeschrittene Aussagen und Anwendungen der diskreten Mathematik, die
wir uns mit Methoden aus der Algebra und der Topologie
erschließen werden. Wir werden diskrete Strukturen (Graphen,
Mengensysteme, Partitionen, Permutationen, etc.) mit Hilfe von
algebraischen/topologischen Objekten (Gruppen, Matrizen, stetigen
Abbildungen, etc.) modellieren und mittels Sätzen aus dem jeweiligen
Gebiet (Struktur abelscher Gruppen, verallg. Mittelwertsätze)
Rückschlüsse ziehen.
Die gewonnen, z.T. tiefgründigen Resultate führen zu interessanten und
unerwarteten Anwendungen in anderen Gebieten zu geben. Zum Beispiel werden
wir...
Vorlesung: | Dienstag | 14 - 16 Uhr | VIRTUELL! |
Übung: | Montag | 10 - 12 Uhr | VIRTUELL! |
Blatt 1 |
Blatt 2 |
Blatt 3 |
Blatt 4 |
Blatt 5 |
9. Februar | Gewicht und Level; kritisches Polynom; Deletion-Contraction für zur Senke inzidente Kanten; Tutte-Grothendieck Invarianten und Tutte-Polynome; Level und externe Aktivität |
2. Februar | Cluster-Feuerung und superstabile Zustände; Energie; Satz: Superstab Konfigurationen sind die eindeutigen Energieminimierer in jeder Feuer-Äquivalenzklasse; Dualität von kritischen und superstabilien Konfigurationen; Dhar's Burning Algorithm; Umsetzung mit Tiefensuche und Bijektion zu aufspannenden Bäumen |
26. Januar | Feuer-äquivalenz von Konfigurationen; Satz: Bijektion zwischen Äquivalenzklassen und kritischen Konfigurationen; Satz: Anzahl krit. Konfigurationen = Anzahl aufsp. Bäume [Kli]; Exkurs: Gitter, Äquivalenzklassen, fundamental Parallelepipede |
19. Januar | azyklische Orientierungen und Stabilisierung; Dauer (Anzahl Feuerungen) bis zur Stabilisierung; Motivation von Senken; kritische Konfigurationen [Kli] |
12. Januar | Chip-firing games; stabile Zustände und globale Konfluenz; Stabilisierung in Abhängigkeit der Anzahl Chips [Kli] |
15. Dezember | Bäume und aufspannende Bäume; (reduzierte) Laplace Matrizen; Matrix-Tree Theorem; Satz von Binet-Cauchy; Indizenzmatrizen [Sta] [HW] |
8. Dezember | Färbungen und chromatische Zahlen; Kneser Graphen; untere Schranke an chromatische Zahl mit dem Satz von Borsuk-Ulam; Gale's lemma |
1. Dezember | Beweis des Ham Sandwich; Ham Sandwich für endliche Punktmengen; Splitting Necklaces |
24. November | Simplexe und Sperner's Lemma in allen Dimensionen; Satz von Borsuk-Ulam und Variationen; Ham Sandwich Theorem [Mat] |
17. November | Das Spiel HEX; HEX-Theorem: Es gibt kein Unentschieden; Beweis mit Sperner's Lemma; algorithmischer Beweis; Literatur [Gale], [BMZ]; Kuchen fair aufteilen für 2 und 3 Personen; Literatur [Su] |
10. November | baryzentrische Unterteilungen und maximale Kantenlängen; Brouwer'scher Fixpunktsatz aus dem Sperner Lemma; Kombinatorischer Beweis des Sperner Lemmas via Graphen und Handshake Lemma; algorithmischer Beweis; Literatur: [AZ] |
3. November | Dreiecke und Unterteilungen/Triangulierungen; Sperner-Färbungen und Regenbogendreiecke; Sperners Lemma; Homöomorphie und der Brouwer'sche Fixpunktsatz; Stückweise lineare Abbildungen und Sperners Lemma aus dem Fixpunktsatz |