Gitterpunkte in Polyedern (Diskrete Geometrie III)

Andreas Paffenholz

Überblick

Wir betrachten ganzzahlige Punkte in Polyedern, ihre Struktur und ihre Klassifikation, mit Anwendungen in der Algebra, linearen Optimierung und Zahlentheorie sowie Algorithmen.

Die Vorlesung findet zweimal wöchentlich mit begleitenden Übungen statt.

Themen

In dieser Vorlesung beschäftigen wir uns mit Gitterpunkten in Polyedern und einigen Anwendungen, in denen solche Strukturen auftauchen. Gitter sind diskrete Untergruppen des \(\mathbb{R}^n\), z.B. das Gitter \(\mathbb{Z}^n\) der Punkte mit ganzzahligen Koordinaten. Ein Polytop, also die konvexe Hülle endlich vieler Punkte, ist ein Gitterpolytop, wenn diese Punkte Gitterpunkte sind.

Wir untersuchen die Struktur solcher Polytope im Verhältnis zum Gitter, bestimmen charakteristische Eigenschaften, und untersuchen die vielfältigen Anwendungen in anderen Gebieten.

Geplante Themen sind:

• Gitterpolytope in kleinen Dimensionen
• Ehrharttheoie
• Klassifikationen von Gitterpolytopen
• Hilbertbasen
• Der Algorithmus von Barvinok
• Flatness Theorem und ganzzahlige lineare Programmierung
• Triangulierungen

Sie sollten sich in Linearer Algebra auskennen. Polyedertheorie ist hilfreich, die notwendigen Kenntnisse können bei Bedarf aber in der Vorlesung kurz eingeführt und in den ersten Tutorien vertieft werden.

Literaturauswahl

1. Barvinok, Alexander: A course in convexity. Graduate Studies in Mathematics. 54. Providence, RI: American Mathematical Society (AMS). x, 366 p. (2002).
2. Barvinok, Alexander: Integer Points in Polyhedra. Zurich Lectures in Advanced Mathematics. European Mathematical Society (EMS), 2008.
3. Bruns, Winfried; Gubeladze Joseph: Polytopes, Rings, and K-Theory. Springer 2009.
4. Beck, Matthias; Robins, Sinai: Computing the continuous discretely. Integer-point enumeration in polyhedra. Springer Undergraduate Texts in Mathematics
5. De Loera, Jesus; Hemmecke, Raymond, Köppe, Matthias: Algebraic and Geometric Ideas in the Theory of Discrete Optimization
6. Schrijver, Alexander: Theory of linear and integer programming. Repr. Chichester: Wiley. xi, 471 p. (1998)
7. Sturmfels, Bernd: Gröbner bases and convex polytopes. University Lecture Series. 8. Providece, RI: American Mathematical Society (AMS). xi, 162 p. (1996).
8. Ziegler, Günter M.: Lectures on polytopes. Graduate Texts in Mathematics, 152. Springer-Verlag, New York, 1995.