Seminar: Discrete Geometry - Beyond the basics

Summer Semester 2013/2014

Arnau Padrol, Raman Sanyal



July 5-6 (no weekly meetings).


In this seminar we will explore advanced notions and constructions from discrete geometry. In particular, we will explore connections to other areas. Students should have a good background in discrete geometry or discrete mathematics (such as ‘Discrete Geometry I’ or ‘Discrete Mathematics I’).

This will be a block seminar (all talks on 5-6 July).

Language: English/German

The organizational meeting will be in the first semester week.

If you are interested in the seminar sign-up at:



Saturday 5.7.2014 morning session (9:00 - 12:30)

Who What References
Secondary polytopes
Gelfand, Kapranov, and Zelevinsky introduced a construction that maps each triangulation of a polytope P with n vertices into a point in R^n. The convex hull of these points is called the secondary polytope of P and has a remarkable combinatorial structure. The vertices of the secondary polytope are in correspondence with regular triangulations of P, and two of them are linked with an edge if and only if the corresponding triangulations are related by a bistellar flip.
Fiber polytopes
Fiber polytopes are an amazing generalization of secondary polytopes. While secondary polytopes concern regular subdivisions, those induced by the projection of a simplex onto the polytope, fiber polytopes reflect the combinatorial structure of coherent subdivisions induced by a general projection of polytopes P ---> Q.
An hom-polytope captures the set of all affine maps between two polytopes. While its facets have a well understood geometric explanation, understanding its vertices is still a big challenge.

Saturday 5.7.2014 afternoon session (13:30 - 18:00)

The universal polytope and equidecomposability
The universal polytope of a polytope P is a polytope associated to all triangulations of P (not only the regular ones). A polytope is called equidecomposable if all its triangulations have the same number of simplices. The universal polytope is used to prove a combinatorial characterization of equidecomposable polytopes.
The associahedron is another remarkable polytope. Its vertices have different combinatorial interpretations: they correspond to the different ways to bracketing a string of letters, binary trees, triangulations of a polygons,...
The Sylvester-Gallai theorem states that for any set of points in the plane, not all of them in a common line, there is a line that goes exactly through 2 points. This theorem admits a lot of interesting proofs. Once proved, a natural question is how many of these lines exist.
Colorful combinatorics
Charathéodory's Theorem states that if a point x is in the convex hull of a set X in R^d, then there is a subset of X of at most d+1 points that contains x in its convex hull. It has a colorful version, where the points of X are colored and we require the subset to be rainbow. It can be used to prove Tverberg's theorem, which also admits a colorful version.

Sunday 6.7.2014 morning session (10:00 - 13:00)

Rigidity and the Lower Bound Theorem
The lower bound theorem characterizes those simplicial polytopes with the minimal number of facets. Kalai's beautiful proof is based on Cauchy's rigidity theorem.
Permutation polytopes
The Birkhoff polytope is the convex hull of the nxn permutation matrices and has a nice halfspace representation as the set of doubly stochastic matrices. More generally, a permutation polytope is the convex hull of a subgroup of the nxn permutation matrices. These can be, however, much more complicated.
Geometric constructions
In his study of projectively unique polytopes, McMullen introduced the polyhedral operations of subdirect sums and products. The latter can be further generalized as a special case of wedge products.