Vorlesung

Algebraische und topologische Methoden
in der Diskreten Mathematik (BaM-DAM-k)

Wintersemester 2020/21

Prof. Raman Sanyal, Sebastian Manecke



Was

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

Eine hübsche (und auf den ersten Blick wenig 'diskrete') Anwendung ist der folgende berühmte Satz: Für jedes in die Luft geworfene Schinken-Käse-Brötchen gibt es einen geradlinien Schnitt (z.B. mit einem Schwert), so dass der Schinken, der Käse und das Brot perfekt halbiert wird.

Teilnahmevoraussetzungen sind BaM-CM, BaM-AN2 und BaM-LA2. Weiteres Wissen zu diskreten Strukturen, Algebra und Topologie über die Pflichtveranstaltungen des 1+2.Semesters hinaus ist hilfreich aber nicht vorausgesetzt.

Sollten Sie Interesse haben an der Vorlesung teilzunehmen, dann schicken Sie bitte Prof. Sanyal (sanyal@math.uni-...) eine Email.

Blockseminar

Am Ende des Semesters wird es ein Blockseminar geben in dem Themen aus der Vorlesung vertieft werden. Wenn Sie Interesse an einer Teilnahme haben, dann schreiben Sie das bitte in Ihrer Email. Für die Ausarbeitungen und Präsentationen im Blockseminar gibt es hier LaTeX Vorlagen und Beispiele.

Wann und wo

Vorlesung: Dienstag 14 - 16 Uhr VIRTUELL!
Übung: Montag 10 - 12 Uhr VIRTUELL!

Spielregeln

Übungsaufgaben

Die Übungsblätter werden in der Übung besprochen.

Blatt 1
Blatt 2
Blatt 3
Blatt 4
Blatt 5

Was bisher geschah

Für die handschriftlichen Notizen zu den Vorlesungen auf die entsprechenden Daten klicken. Die Tafelbilder der gesamten Vorlesung gibt es hier Username/Passwort gibt es auf Anfrage.

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

Literatur

Wird im Laufe der Vorlesung bekannt gegeben.


Impressum Datenschutzerklärung