Die Vorlesung ist eine Einführung in die diskrete und konvexe Geometrie. Unter anderem werden Polyeder, Komplexe, Arrangements, Seitenflächenstrukturen, Zerlegbarkeit (Unterteilungen, Minkowskisummen), Gitterpunkte und Volumen, geometrische Ungleichungen, diskrete Geometrie (Radon, Helly, Tverberg), Anwendungen (Optimierung, Algebra) betrachtet.
Link zum Vorlesungsverzeichnis.| Vorlesung: | ||
| Dienstag | 10 - 12 Uhr | RM10 101 |
| Mittwoch | 10 - 12 Uhr | RM10 101 |
| Übung: | ||
| Donnerstag | 12 - 14 Uhr | RM10 901 |
| Freitag | 16 - 18 Uhr | RM10 902 |
| Abgabe: 24. Oktober | Blatt 1 |
| Abgabe: 7. November | Blatt 2 Sage Notebook Sage Notebook Einführung |
| Abgabe: 14. November | Blatt 3 |
| Abgabe: 28. November | Blatt 4 Sage Notebook |
| Abgabe: 5. Dezember | Blatt 5 |
| Abgabe: 12. Dezember | Blatt 6 |
| Abgabe: 19. Dezember | Blatt 7 |
| Abgabe: 16. Januar | Blatt 8 |
| Abgabe: 23. Januar | Blatt 9 |
| Abgabe: 6. Februar | Blatt 10 |
| 29/30. Jan. |
Gale Transformierte von Vektorkonfigurationen; azyklische und total zyklische
Konfigurationen; spitze Kegel und azykl. GTs; Koseiten und Charakterisierung
in GTs; Gale Transformierte von Polytopen via Homogenisierung; Klassifikation
von d-Polytopen mit d+2 Ecken
GTs charatertisieren Vektorkonfigurationen bis auf lineare Transformation; bei Polytopen bis auf affine Äquivalenz; Projektive Transformationen und GTs von Polytopen; Löschung und Kontraktion auf GTs; Unterpolytope und Eckenfiguren; Affine Gale Transformierte / Affine Gale Diagramme; Konstruktion und Charakterisierung von Koseiten; Beispiele |
| 22/23. Jan. |
Schälbare Simplizialkomplexe; schälbar impliziert
partitionierbar; Ränder
simplizialer Polytope sind schälbar; UBT mit
Gleichheitsbedingung gilt für
schälbare und Eulersche Komplexe
g-Vektoren von einfachen/simplizialen Polytopen; Multimengen und Multikomplexe; O-Sequenzen; g-Theorem: g-Vektor von simplizialem Polytop gdw O-Sequenz; Charakterisierung von O-Sequenzen und f-Vektoren von Simplizialkomplexen; Beispiel: f-Vektoren von Graphen |
| 15/16. Jan. |
Lower Bound Problem für allgemeine Polytope: schwierig!;
Einschränken auf einfache/simpliziale Polytope; Operationen
"truncation" und "stacking"; Lower Bound Theorem; MPW-Reduktion:
es reicht (d-2)-Seiten zu betrachten; Formulierung via
h-Vektoren und Beweisidee von Blind-Blind
Simpliziale Version und Starrheit von Gerüsten; Infinitesimale Starrheit und Rang der Jakobimatrix; Sätze von Cauchy und Dehn; geometrische und abstrakte Simplizialkomplexe; rein, starker Zusammenhang und Pseudomannigfaltigkeiten; Lower-Bound-Theorem mit Gleichheitsfall für normale Pseudomannigfaltigkeiten; h-Vektoren und partitionierbare Komplexe |
| 18/19. Dez. |
Euler-Poincare Formel und Euler Charakteristik; Euler
Charakteristik ist eine Bewertung; Cayley Polytope; Euler
Charakteristik von Pyramiden; Beweis Euler-Poincare Formel;
keine weiteren linearen Relationen auf f-Vektoren; Beweis durch
Konstruktion und Kombinatorik von f-Polynomen
f-Vektoren von einfachen Polytopen; h-Vektor via guten Orientierungen; f-Vektor rekonstruierbar; h-Vektor unabhängig von Orientierung; Motzkins "Upper Bound Conjecture" und McMullens Beweis |
| 11/12. Dez. |
Einbettung von planaren Graphen mittels "Gummibändern" (Tutte
Embedding); Gibt Einbettung mit festem Rand und konvexen
beschränkten Gebieten; Einbettung gibt auch Möglichkeit zum
"liften" in drei Dimensionen; Konsequenzen: Kombinatorik von
3-Polytopen lässt sich rational realisieren; Isotropie Vermutung
ist in drei Dimensionen richtig; Form einer Facette kann
vorgeschrieben werden; Satz: Seitenflächenverband eines
einfachen d-Polytops aus dem Graphen rekonstruierbar; azyklische
und gute Orientierungen
initale Untergraphen und Facetten; Perles Vermutung: induzierte, (d-1)-reguläre und nicht-trennende Untergraphen sind genau Facetten; Falsch in Dimension 4; f-Vektoren von 3-Polytopen; Satz von Steinitz: f-Vekotren von 3-Polytopen sind genau Gitterpunkte in einem 2-dimensionalen Kegel; Falsch in jeder Hinsicht in Dimension 4 |
| 4/5. Dez. |
Graphen von Polytopen; Zusammenhang und Nachbarn mit höherem
Zielfunktionswert; Normalen- und Tangentialkegel; Satz von
Balinski; Diskret-geometrische Perspektive auf den
Simplex-Algorithmus; Durchmesser von Graphen und Hirsch
Vermutung
Graphen von 3-Polytopen; induzierte und nicht-trennende Kreise geben 2-Seiten; Polyedrische Komplexe und Schlegel-Diagramme; Graphen von 3-Polytopen sind planar; Satz von Steiniz; duale Graphen und polare Polytope; Eulers Polyeder Formel; Realisierungen durch Y-Delta-Operationen |
| 27/28. Nov. |
Atome und atomische Verbände; koatomische Verbände und duale
Posets; Seitenflächenverbände sind (ko)atomisch; Bool'sche
Verbände und geordnete Partitionen; Ketten und graduierte
Posets; Diamant-Eigenschaft; eulersche Posets;
Charakterisierungsproblem von Seitenflächenverbänden;
Klammerausdrücke, binäre Bäume, Dyck-Pfade, Triangulierungen
von Polygonen; Assoziaeder
zyklische Polytope und univariate Polynome; allgemeine Lage und simpliziale Polytope; k-nachbarschaftliche Polytope; zyklische Polytope sind nachbarschaftlich; k-Skelett und kubisch-nachbarschaftliche Polytope; f-Vektoren und Nachbarschaftlichkeit |
| 20/21. Nov. |
doppelt-stochastische Matrizen und Birkhoff Polytope:
Dimensionen, irredundante Ungleichungen, Ecken (Birkhoff-von
Neumann), Seiten und elementare Graphen; perfekte Matching
Polytope von (bipartiten) Graphen; Permutaeder ist Projektion
vom Birkhoff Polytope; Anzahlen Facetten; Satz von
Schur-Horn Seiten und assoziierte Seiten; Eigenschaften; Kreuzpolytope; simpliziale Polytope; kombinatoische Isomorphie und Pertubationen; einfache und simpliziale Polytope; Posets; Hasse Diagramme; Supremum/Infimum; Verbände und Seitenflächenverband |
| 13/14. Nov. |
Alle Seiten von Polyedern sind
exponiert; Seiten von Polytopen durch bestimmte Teilmengen von
Ecken bestimmt; Beispiel: Simplex; Ungleichungen und
Stützhyperebenen von Polyedern; irredundante Ungleichungen und
Facetten; Dimension und affine Hülle von Seiten; einfache
Polytope und Eckenfiguren; Beispiel Würfel großes Beispiel: Das Permutaeder; Dimension, Ecken, Ungleichungen |
| 6/7. Nov. |
Kegelpolarität und Eigenschaften; Bipolarsatz; Polarität unter
Schnitten und Vereinigungen; Beweis: endlich erzeugte Kegel
sind polyedrisch; Rezessionskegel, Linienräume, spitze
Polyeder; Polarität für Polyeder; Würfel und Kreuzpolytope;
Inneres und relativ Inneres von Polyedern Seiten von konvexen Mengen; echte Seiten sind Teilmenge vom Rand; Seiten von Seiten und Schnitte; exponierte Seiten sind Seiten (aber i.A. nicht umgekehrt); jeder Punkt im Rand liegt in einer (exponierten) Seite; Rand ist disjunkte Vereinigung von Seiten; Seiten von Minkowskisummen und Polyedern; Schnitte von exponierten Seiten; |
| 30/31. Okt. |
Eigenschaften von Stützfunktionen und Charakterisierung;
Monoid: Konvexe Körper mit Minkowskisumme; Monoide mit
Kürzungsregel Polyeder als endliche Schnitte von Halbräumen; Lineare Optimierungsprobleme; Gute Charakterisierungen und Farkas Lemma; LP-Dualität endlich erzeugte Kegel; Fundamentalsatz der Polyedertheorie (Minkowski-Weyl); polyhedrische Kegel; MW für Kegel; Kegel-MW und MW sind äquivalent; Erste Hälfte: polyhedrische Kegel sind endlich erzeugt |
| 23/24. Okt. |
Satz von Caratheodory: Interpretation und Anwendung; Polytope sind
Projektionen von Simplexen; Lemma von Radon und Satz von Helly;
Helly für unendliche Familien Innere Punkte, relativ Inneres und Dimension; Darstellung relativ-innerer Punkte in Polytopen Hyperebenen und Halbräume; Trennungssatz; zulässige Hyperebenen und Stützhyperebenen; Stützfunktionen konvexer Körper |
| 16/17. Okt. |
Teaser diskrete und konvexe Geometrie: Permutaeder, Stirling
Zahlen, Volumen
und aufspannende Bäume, Gitterpunkte und Wälder, Diagonalen
symm. Matrizen lineare (Unter)Räume: lineare Kombinationen, lineare Hülle, Basen, lineare Abhängigkeit, Dimension, lineare Transformationen affine (Unter)Räume: affine Kombinationen, affine Hülle, affine Basen, Dimension; affine Transformationen Konvexität: Segmente und konvexe Mengen; Beispiele: konvexe Funktionen und Epigraphen, Normen und Bälle, positive Polynome, positiv semidefinite Matrizen; Operationen auf konvexen Mengen: Schnitte, Produkte, Minkowskisummen; (Ur)Bilder konvexer Mengen unter affine Abbildungen; konvexe Hülle und konvex Kombinationen; extremale Punkte und Satz von Minkowski; konvexe Körper und Polytope; Satz von Caratheodory |
Lectures on polytopes. Günter Ziegler
A course in convexity. Barvinok, Alexander
Convex polytopes. Branko Grünbaum
Convex and discrete geometry. Peter Gruber
Combinatorial Reciprocity Theorems. Matthias Beck, Raman Sanyal