Was

Polytope sind konvexe Körper, die in praktisch allen mathematischen Gebieten auftreten. Insbesondere ihre Beschreibung als konvexe Hülle von endlich vielen Punkten oder als Lösung eines Systems von endlich vielen linearen Ungleichungen machen sie attraktiv für die Optimierung und die geometrische Modellierung. Zur weiteren Verarbeitung zum Beispiel in der Numerik oder algorithmischen Geometrie/Computergraphik werden geometrische Objekte "trianguliert", also zerlegt in elementare Polytope (meist Simplexe). Bekannt und beliebt sind Delaunay Triangulierungen von Punktmengen und Voronoi Zerlegungen (und Power Diagrams) des Raums. Aber auch in der Algebra, der Kombinatorik und der diskreten/algebraischen Geometrie spielen Zerlegungen und auch der "Raum" aller Zerlegungen eine wichtige Rolle. Besonders faszinierend ist, zum Beispiel, der Zusammenhang zwischen Polygonen, Catalan Zahlen und Assoziaedern.

In diesem 1-wöchigen Blockkurs werden wir uns mit der Geometrie und Kombinatorik von Polytopen und Triangulierungen beschäftigen und dabei ausgewählte Anwendungen kennenlernen. Nach einer Einführung in Polytoptheorie werden grundlegende Verfahren zur Triangulierung erarbeitet und auf Probleme in der algorithmischen Geometrie, der Kombinatorik und, je nach Wissensstand, der Algebra angewendet. Im dem Kurs wird der "pratische" Charakter betont: am Computer kann ausprobiert, nachvollzogen und, insbesondere, experimentiert werden.

Die mathematischen Voraussetzungen für den Blockkurs sind ein solides Wissen und Verständnis zur linearen Algebra und diskreten Mathematik. Vorausgesetzt wird aber auch die Bereitschaft in Rahmen des Blockkurs hart zu arbeiten und sich intensiv mit dem Material auseinander zu setzen. Es wird 2 Vorlesungen pro Tag geben und im Anschluss Übungen (auch am Computer). In Abprache mit den TeilnehmerInnen wird es zu bearbeitende Projekte geben.

Wann und wo

Spielregeln

• Im Rahmen der Projekte und der Übungen werden wir Sage verwenden. Um einen möglichst reibungsfreien Ablauf zu ermöglichen, ist es hilfreich, wenn Ihr, soweit möglich, euch Sage auf eure Laptops installiert. Alternativ ist es auch möglich, mit einem Account bei Cocalc Sage zu verwenden.
• Es wird weiter unten handschriftliche Vorlesungsnotizen geben.

Projekte (Link zu den Projektbeschreibungen)

• Jeder ist für ein Projekt zuständig, man kann aber darf natürlich gern auch über die anderen Projekte nachdenken! Wer für welches Projekt verantwortlich ist, wird im Anschluss an die erste Vorlesung geklärt.
• Jedes Projekt besteht aus drei Meilensteinen. Zu jedem dieser Meilensteine wird es ein Treffen geben, bei welchem Ihr eure Überlegungen zu den einzelnen Aufgaben darlegt.
• Die Projekte müssen nicht während der Blockvorlesung bearbeitet werden. Ihr habt danach noch reichlich Zeit daran zu arbeiten. Nach jedem Meilenstein gibt es ein Treffen pro Projekt.
• Die Projekte sind mit den Mitteln aus der Blockvorlesung machbar, aber es geht bei den Projekten auch darum durch experimentieren auf die Dinge zu stoßen, die bewiesen werden müssen. (Aufgaben vom Typ “Zeige, dass” gibt es verhältnismässig wenig.)
• Wir geben gerne Tipps und Hilfestellungen!
• Wir können euch natürlich nicht daran hindern nach den Lösungen zu googlen. Das wird bei ein paar der Aufgaben klappen aber bei den meisten sicher nicht. Unsere Empfehlung ist, dass ihr es selber probiert - sowohl die SAGE Experimente als auch die Mathematik.

Was bisher geschah

12. März	Konvexität, konvex Hülle, Polytope; Eckenmengen; affine Räume, affine Unabhängigkeit, Dimension von Polytopen, Beispiele: Würfel und Simplexe; Lemma: Jedes Polytop ist Projektion eines Simplex; Permutaeder und Satz von Schur-Horn; Satz von Caratheodory Hyperebenen und Halbräume; Trennungssatz; Polyeder als Schnitte endlich vieler Halbräume; Farkas Lemma; endlich erzeugte Kegel
13. März	Lineare Programmierung und Dualität (aus Farkas Lemma); Satz von Minkowski-Weyl und Konsequenzen; Beipsiele: Simplexe, Würfel, Kreuzpolytope; Birkhoff Polytope Seitenflächen; Ecken, Kanten, Grate (ridges), Facetten; Eindeutige Darstellung durch Ecken; Seitenflächen von Simplexen; Schnitte von Seiten und Seiten von Seiten; Seitenflächenverband; Alternativer Beweis vom Satz von Caratheodory; Graphen von Polytopen
14. März	Graphen von Polytopen; Orientierungen durch lineare Funktionen; Satz(Balinkski): Graph von d-Polytop ist d-zusammenhängend; geometrische Perspektive auf lineare Programmierung: Laufen auf orientiertem Graphen; Graphen von Kreuzpolytopen und Permutaedern; (Normalenkegel, Normalenfächer und Minkowskisummen) Volumenberechnung von Polygonen und Triangulierungen; Anzahl Triangulierungen von Polygonen; Zerschneidungen, Unterteilungen und polyedrische Komplexe; Liftings, untere Seiten und reguläre Unterteilungen;
15. März	Beispiel: Kanonische Zerlegung des d-Würfels als reguläre Unterteilung; alle Unterteilungen von Polygonen (ohne neue Ecken) sind regulär; im Allgemeinen gibt es nicht-reguläre Unterteilungen; Antisterne und Ecken pullen; Pullen ist regulär; Pulling-Triangulierung: konkrete und kombinatorisch; Beispiel: Würfel; Interessante Eigenschaft: Alle Pulling-Triangulierungen von Würfeln haben die gleiche Anzahl Zellen; (Pushing-und Delaunay-Unterteilungen) Welche Höhenvektoren gebene gleiche Unterteilungen; Satz: Das Sekundärpolytop parametrisiert alle regulären Unterteilungen; Definition durch GKZ-Vektoren; Beispiel: 5-Eck; Benachbarte Ecken entsprechen Flips;
16. März	Konstruktion des Sekundärpolytops: Stückweise-lineare (PL) Interpolation auf Polytopen; Integrale von PL-Funktionen und konvexe PL-Funktionen; Konsequenz: Reguläre Triangulierungen sind Ecken des Sekundärpolytops; Kreise und Flips im Allgemeinen; Andere Perspektive auf reguläre Unterteilungen via Projektionen: Unterteilungen sind Projektionen bestimmter Auswahlen von Seiten eines Simplex; Kohärente Auswahl an Seiten via linearer Funktionen Verallgemeinerung: Polytope als Projektionen anderer Polytope und induzierte Unterteilungen; Faserpolytope als Parameterräume solcher Unterteilungen; Spezialfall: Monotone-Pfad-Polytope; monotone Pfade und kohärente Pfade; Beziehung zur linearen Programmierung (shadow-vertex-rule); Beispiel: Würfel und Permutaeder; Konstruktion via Ecken; Konstruktion via Schnitten und Minkowskisummen

Sage Code

Literatur

[CRT]

Combinatorial Reciprocity Theorems. Matthias Beck, Raman Sanyal