matthias beck

FU Berlin Winter 2020/21

Course description. This is the first in a series of three courses on discrete geometry. The aim of the course is a skillful handling of discrete geometric structures including analysis and proof techniques. The material will be a selection of the following topics:

• Polyhedra and polyhedral complexes
• Configurations of points, hyperplanes, subspaces
• Subdivisions and triangulations (including Delaunay and Voronoi)
• Polytope theory
• Representations and the theorem of Minkowski-Weyl
• Polarity, simple/simplicial polytopes, shellability
• Shellability, face lattices, f-vectors, Euler- and Dehn-Sommerville
• Graphs, diameters, Hirsch (ex-)conjecture
• Geometry of linear programming
• Linear programs, simplex algorithm, LP-duality
• Combinatorial geometry / Geometric combinatorics
• Arrangements of points and lines, Sylvester-Gallai, Erdos-Szekeres, Szemeredi-Trotter
• Arrangements, zonotopes, zonotopal tilings, oriented matroids
• Examples, examples, examples
• Regular polytopes, centrally symmetric polytopes
• Extremal polytopes, cyclic/neighborly polytopes, stacked polytopes
• Combinatorial optimization and 0/1-polytopes

Prerequisites. Linear algebra.

References. We will mostly follow

• G. M. Ziegler, Lectures in Polytopes, Springer 1995

but also cover some sections of

• M. Beck and R. Sanyal, Combinatorial Reciprocity Theorems, American Mathematical Society 2018
• J. Matousek, Lectures on Discrete Geometry, Springer 2002

Online musings. The FU currently does not allow our course to be in person, so I will stream (and record) every lecture via FU WebEx. Please check the FU guidelines dealing with the Corona virus frequently. The exercise discussions will also be on FU WebEx; see the FU Whiteboard for more information and a link to our class sessions.

Exercises & final exam. We will post (on the FU Whiteboard sites) weekly homework problems; they will be due each Friday. To obtain the Aktive Teilnahme stamp, you will need to reach at least a 50% total score on the homework. The final exam is a 48-hour take-home exam starting at 12:00 on 9 March 2021, posted here and on the FU Whiteboard sites. The Nachklausur is also be a 48-hour take-home exam starting at 12:00 on 6 April 2021.

I want to ensure that each of you accomplishes the goals of this course as comfortably and successfully as possible. At any time you feel overwhelmed or lost, please come and talk with me. Always ask lots of questions in class; my courses are interactive, whether in person or online.