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

• Am 07. Dezember entfällt die Vorlesung (dies academicus)
• Die erste Vorlesung findet am 16.11. statt, die erste Übung wird voraussichtlich am 21.11. durchgeführt werden.

---

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.

• Welche Arten von Graphenfärbungen und welche chromatischen Zahlen gibt es, welche wird in der Arbeit von Lovasz studiert?
• Leiten Sie mit Hilfe graphentheoretischer Invarianten jeweils eine nicht triviale obere und untere Schranke für die chromatische Zahl her.
• Formulieren Sie Knesers ursprüngliche Fragestellung, erklären Sie diese im graphentheoretischen Kontext und zeigen Sie, dass Ihre in 2) hergeleitete untere Schranke die Vermutung nicht klärt.
• Beschreiben und erläutern Sie den Satz von Lovasz, in welchem eine allgemeine untere Schranke für die chromatische Zahl eines Graphen angegeben wird.
• Erklären Sie, wie Homologiegruppen benutzt werden können, um diese untere Schranke zu berechnen. Formulieren und zitieren Sie die relevanten Sätze ohne Beweis.
• Beweisen Sie die untere Schranke von Lovasz, folgen Sie dabei der Beweisskizze aus [6]. Erklären Sie alle relevanten Schritte und Begriffe.
• Erläutern Sie den Satz von Borsuk-Ulam, der in im Beweis von Lovasz verwendet wird, geben Sie äquivalente Formulierungen an und beweisen Sie diese.

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.

• Erklären Sie die Begriffe Voronoi-Diagramm und Delaunay-Triangulierung für eine endliche Punktmenge des R^3. Was passiert, falls die Punkte nicht in allgemeiner Lage sind?
• Was sind Voronoi-Regionen einer endlichen Menge von (euklidischen) Bällen, was ist der dazu duale Komplex? Wann liegt ein Simplizialkomplex vor? Beschreiben Sie den alpha-Komplex einer endlichen Menge von Bällen und erklären Sie, ob es er eine Filtrierung eines Simplizialkomplexes liefert.
• Warum wird die Summe zweier p-Ketten mit Koeffizienten in Z/2Z durch die symmetrische Differenz der beiden Trägermengen beschrieben?
• Beschreiben die den inkrementellen Algorithmus zur Berechnung der Betti-Zahlen eines filtrierten Simplizialkomplexes und erläutern Sie die Begriffe positiver und negativer Simplex in diesem Zusammenhang.
• Was ist unter der p-persistenten Betti-Zahl beta_k(l,p) zu verstehen, wie werden positive mit negativen Simplexen gepaart und was ist die Persistenz eines k-Zykels bzw des zugehörigen Persistenzpaars?
• Visualisieren Sie die Persistenzpaare und ihre Persistenz mit Hilfe von k-Intervallen und k-Dreiecken. Formulieren und beweisen Sie das Monotonizitätslemma und das Dreieckslemma aus [3]. Wie hilft diese Visualisierung beim Bestimmen einer vereinfachten Filtrierung? Welche Probleme können bei der Vereinfachung auftreten und wie können sie gelöst werden?
• Beschreiben Sie die Schritte 4)-6) an einem konkreten Beispiel, dass Ihnen auf Nachfrage individuell mitgeteilt wird.

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.