Was

Ein Polytop ist die konvexe Hülle endlich vieler Punkte im Euklidischen d-dimensionalen Raum. Entsprechend sind Polytope konvexe und kompakte Mengen, die Polygone und (dreidimensionale) Polyeder verallgemeinern. Polytope werden genutzt um allgemeine konvexe Körper zu approximieren und z.B. auf dem Computer darzustellen.

Äquivalent (aber nicht offensichtlich) lassen sich Polytope als die beschränkte Lösungsmengen von endlich vielen linearen Ungleichungen darstellen. Polytope (und Polyeder) sind somit die zulässigen Lösungen linearer Optimierungsprobleme. Diese geometrische Sichtweise auf die lineare Optimierung wird von nahezu alle Lösungsverfahren (Simplex-Algorithmus, Innere Punkte Methoden, etc.) genutzt.

In dieser Vorlesung wird es um die Geometrie und Kombinatorik von Polytopen gehen. Dabei werden wir uns grundlegende Begriffe und Sätze aus der Polytop-Theorie erarbeiten und sie an wichtigen Beispielklassen aus der Kombinatorik, der linearen/kombinatorischen Optimierung und der (linearen) Algebra anwenden.

Teilnahmevoraussetzungen sind BaM-CM, BaM-AN2 und BaM-LA2. Weiteres Wissen zu diskreten Strukturen, Geometire und Algebra 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.

Wann und wo

Spielregeln

• Die genauen Spielregeln werden in der ersten Vorlesung besprochen (und ggf. an die aktuelle Situation angepasst).
• Es wird jede Woche ein Übungsblatt geben. Ausgabe der Blätter und Abgabe der Lösungen erfolgt über das OLAT. Bitte scannen/fotographieren Sie Ihre Lösungen und laden diese als ein PDF mit Dateinamen NACHNAME-VORNAME_BlattX.pdf hoch.
• Die Modalitäten zur Abschlussprüfung (Klausur oder mündliche Prüfung) werden in den ersten Vorlesungswochen besprochen.
• Es wird handschriftliche Vorlesungsnotizen geben. Diese Notizen sind ohne einen Besuch der Vorlesung vermutlich nicht verständlich, aber sollten helfen den Stoff aus der Vorlesung nachvollziehen zu können.
• Im Rahmen der Übungen werden wir immer Mal wieder auf SAGE zurückgreifen. Um einen möglichst reibungsfreien Ablauf zu ermöglichen, ist es hilfreich, wenn Sie, soweit möglich, sich Sage auf Ihre Laptops installieren würden. Alternativ ist es auch möglich, mit einem Account bei Cocalc Sage zu verwenden.

Literatur

• [BS] Beck, Sanyal. Combinatorial Reciprocity Theorems
• [Mat] Jirka Matousek Lectures on discrete geometry
• [Z] Ziegler. Lectures on polytopes