BannerBannerBanner

Fallstudien der Mathematischen Modellbildung [MA2902] - WS 16/17
Fachgebiet 2: Simplizialkomplexe in der mathematischen Modellbildung

Dies ist die Webseite zu Fachgebiet 2 der Lehrveranstaltung Fallstudien MA2902 im WS2016/17
Link zum Fachgebiet 1 (Optimaler Transport) und Fachgebiet 3 (Röntgenkristallographie)

Aktuelles



top
Vorlesung und Übung
Veranstaltung Turnus Tag Start Zeit Raum Dozent Bemerkungen
Vorlesung wöchentlich Di 22.11. 12:15 - 13:45 MI HS3 PD Dr. Carsten Lange  
Vorlesung wöchentlich Mi 16.11. 17:00 - 18:30 Chemie HS 1 PD Dr. Carsten Lange keine VL am 07.12.
Übung wöchentlich Mo   16:15 - 17:45      

Inhalt
Simplizialkomplexe sind ein sehr flexibles Hilfsmittel der mathematischen Modellierung und ermöglichen die Berechnung verschiedener Invarianten, die wiederum Rückschlüsse auf das ursprüngliche Problem ermöglichen. So können beispielsweise (geschlossene) Flächen klassifiziert, Färbungsprobleme der Graphentheorie studiert oder Messungenauigkeiten in großen Messreihen identifiziert werden.

Die Vorlesung wird einen ersten Einblick in die Modellierung durch Simplizialkomplexe und die Berechnung verschiedener fundamentaler topologischer Invarianten geben.

Vorlesungsunterlagen

Begleitend zur Vorlesung wird ein Vorlesungsskriptum (VL 1-6) angeboten, das im Laufe der Vorlesung erweitert und korrigiert wird.

Aufgabenblätter

Nr. Datum der Übung Blatt
1 21.11.16 Blatt 1
2 28.11.16 Blatt 2
3 05.12.16 Blatt 3
4 12.12.16 Blatt 4
5 19.12.16 Blatt 5

Hausarbeit

Die technischen Details zu den Hausarbeiten.
Bei Fragen zur Themenstellung, Inhalt oder der Literatur wenden Sie sich bitte an PD Dr. Carsten Lange.

Thema 1: Chromatische Zahl von Graphen und simpliziale Komplexe

In vielen Anwendungen der Praxis muss die chromatische Zahl eines Graphen oder einer Graphenfamilie bestimmt oder abgeschätzt werden. Offensichtlich erhält man eine obere Schranke für die chromatische Zahl, indem zulässige Färbungen konstruiert werden. Allerdings stellt sich dann die Frage, ob die Schranke optimal ist oder nicht. Im Rahmen dieses Projekts ist ein allgemeines Verfahren zu beschreiben, mit dessen Hilfe eine untere Schranke für die chromatische Zahl berechnet werden kann. Dieses Verfahren wurde 1978 von Lovasz erstmalig beschrieben und bringt die chromatische Zahl eines Graphen G mit Homologiegruppen eines Simplizialkomplexes in Verbindung, der dem Graphen G assoziiert ist. Der zu Grunde liegende Satz wurde von Lovasz benutzt, um eine Vermutung von M. Kneser aus dem Jahr 1955 zu beweisen.

Bitte bearbeiten Sie in Ihrer Projektarbeit den folgenden Fragenkatalog.

Literatur:
[1] A. Björner: Combinatorics and Topoogy, Notices Amer. Math. Soc., 32 (1985), 339-345.
[2] A. Björner: Topological Methods, in Handbook of Combinatorics (eds. R. Graham, M. Grötschel, and L. Lovasz), North Holland, Amsterdam, 1995, pp. 1819-1872.
[3] M. Kneser: Aufgabe 360, Jber. Deutsch. Math-Verein. 58 (1955).
[4] M. de Longueville: 25 Jahre Beweis der Kneser-Vermutung, DMV-Mitteilungen 2003(4), 8-11.
[5] J. Matousek: Using the Borsuk-Ulam Theorem, Springer-Verlag Berlin, 2003.
[6] L. Lovasz: Kneser's Conjecture, Chromatic Number, and Homotopy, Journal of Combinatorial Theory, Series A, 25 (1978), 319-324 .

Thema 2: Topologische Persistenz und Vereinfachungen

Wird ein Simplizialkomplex nacheinander aus den einyelnen (offenen) Simplexen zusammengesetzt, so ändert sich in jedem Schritt der Konstruktion höchstens eine Betti-Zahl. Ziel der topologischen Persistenz ist eine Quantifizierung, wie "persistent" Homologieelemente in dieser Konstruktion sind, dh für wieviele Konstruktionsschritte sie unterscheidbar bleiben. Mit diesem Maß kann die ursprüngliche Konstruktion so modifiziert werden, dass in der neuen Konstruktion alle auftretenden Homologieelemente eine Persistenz besitzen, die einen vorgegebenen Wert übertrifft. Diese modifizierte Konstruktion ist eine Vereinfachung der ursprünglichen, da einerseits weniger Änderungen der Betti-Zahlen auftreten und andererseits "kleine topologische Störungen" vernachlässigt werden. Dadurch werden wesentliche Eigenschaften hervorgehoben, die dann zu einer Analyse der Daten verwendet werden können.

Bitte bearbeiten Sie in Ihrer Projektarbeit den folgenden Fragenkatalog. Um einige technische Details zu vermeiden, sind ausschließlich endliche Simplizialkomplexe im 3-dimensionalen Raum und Homologiegruppen mit Koeffizienten in Z/2Z zu betrachten.

Literatur:
[1] C. J. A. Delfinado und H. Edelsbrunner: An incremental algorithm for Betti numbers of simplical complexes on the 3-sphere, Comput. Aided Geom. Design 12 (1995), 771-784.
[2] H. Edelsbrunner und J. Harer: Computational Topology, American Mathematical Society Providence, 2010.
[3] H. Edelsbrunner, D. Letscher und A. Zomorodian: Topological Persistence and Simplification, Discrete Comput. Geom. 28 (2002), 511-533.
[4] H. Edelsbrunner und E. P. Mücke: Three-dimensional alpha shapes, ACM Trans. Graphics 13 (1994), 43-72.