# 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.