Discrete Geometry I - Diskrete Geometrie I

Summer Semester 2022

Lecturer: Marta Panizzut
TA: Sandro Roch


VL: Monday 10-12 (MA 141)
VL: Tuesday 14-16 (EB 202)
Üb: Thursday 14-16 (EW 203)


Exercises will be posted weekly. The solutions will be discussed during the exercise sessions. The exercise sessions will also complement the lectures with more examples and results.

This is a BMS Basic Course, which will thus be given in English.

Please register via email to the course.

Contents

The course will cover the following topics:
  • Definitions of polytopes
  • Face lattices of polytopes
  • Graphs of polytopes
  • Linear programming and the simplex algorithm

References

  • Joswig and Theobald: Polyhedral and Algebraic Methods in Computational Geometry, Springer 2013.
  • Ziegler: Lectures on Polytopes, Springer 1995.
References are available as e-books at TU Library.

Exams

Oral exams will take place in the following days from 09:00-12:30:
  • Thursday, July 28,
  • Friday, July 29,
  • Monday, August 1, and
  • Tuesday, August 2.
Please send an email by Monday, July 25 to register. The exams will last ~30 minutes. In the first 10 minutes students will be asked to present a topic of their choice.

A second round of exams will take place at the end of September. More precise information will be added here and shared via email with registered students.

Overview of lectures and exercise sessions

  • Week 1: April 25 - 28
    Lectures: Introduction to the course. Linear, affine and convex hulls and related defintions. V-polytopes and their faces.
    Exercises: Exercise Sheet 1 and Carathéodory's Theorem [Chapter 1.6, Zie].
  • Week 2: May 2 - 5
    Lectures: Separating hyperplanes and separation theorems [Appendix B, JT], and the faces of a polytope [Chapter 3.1.1 and 3.1.2, JT]
    Exercises: Exercise Sheet 2
  • Week 3: May 9-12
    Lectures: H-representation of polytopes and the representation theorem of polytopes [Chapter 3.1.3, JT]. Introduction to face lattice and Combinatorial type of polytopes.
    Exercises: Exercise Sheet 3 and Radon's and Helly's Theorems.
  • Week 4: May 16-19
    Lectures: The face lattice of a polytope [Chapter 3.2, JT]. Important example: simplicies.
    Exercises: Exercise Sheet 4
  • Week 5: May 23-26
    Lectures: duality and polarity [Chapter 3.3, JT]
    No exercise session on Thursday, May 26.
  • Week 6: May 30-June 2
    Lectures: Bounds on entries of f-vectors and Euler's formula [Chapter 3.4, JT].
    Exercises: Exercise Sheet 6 and cyclic polytopes [Theorem 0.6, Zie]
  • Week 7: June 6-9
    No lecture on Monday, June 6.
    Lecture: Cyclic polytopes and the upper-bound theorem [Chapter 3.5, JT].
    Exercises: Exercise Sheet 7
  • Week 8: June 13-16
    Lectures: Introduction to linear programming, graphs of polytopes and comments on Hirsch's conjecture [Chapter 4.1, JT] and [Chapter 3.2, Zie].
    Exercises: Exericse Sheet 8
  • Week 9: June 20-23
    No lectures and exercise session.
  • Week 10: June 27-30
    Lectures: Duality of linear programs and the simplex algorithm [Chapters 4.2 and 4.3, JT]
    No exercise session on Thursday, June 30.
  • Week 11: July 4-7
    Lectures: Balinski's Theorem [Thm 3.14, Zie], Kalai's simple way to tell a simple polytope from its graph [Thm 3.12, Zie], bound on the diameter of 0/1 polytopes [Thm 3.11, Zie]
    Exercises: Exercise Sheet 10
  • Week 12: July 11-14
    Lectures: Simplex algorithm and how to compute a start vertex [Chapters 4.3 and 4.4, JT], few comments on convex hull computations.
    Exercises: Exercise Sheet 9
  • Week 13: July 18-21
    Lecture and exercise session: More topics in discrete geometry.