Inhalt:

Extensions of polytopes The extension complexity of a polytope P is the minimal number of facets of a polytope Q that linearly projects onto P. This rather simple definition has interesting consequences and relations to areas such as discrete geometry, combinatorial optimization, information theory, and linear algebra. Determining the extension complexity of a polytope is extremely hard (even for polygons!) and obtaining exact values or even just bounds for special polytopes is an active area of research. The goal of the seminar is to develop a good understanding of extension complexity and the notions related to it. Topics might include

• geometry of extensions: sections, projections, and duality
• relations to the nonnegative rank of matrices
• lower bounds via coverings and chromatic numbers
• bounds via communication protocols
• special instances: permutahedra, matching polytopes, etc.
• other notions of extensions: the positive semidefinite and cone ranks

The seminar is aimed at students with an interest in discrete and convex geometry, discrete mathematics / combinatorial optimization, and linear algebra. The prerequisites for most topics is a basic understanding of polytopes (such as Discrete Geometry I).

The first meeting of the seminar will take place during the first week of the semester.

Extensions of polytopes