1995/01/01 by Günter M. Ziegler · 1,584 citations
Computer Science · Mathematics · Social Sciences · #Algebra over a field #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Geometry #Mathematical proof #Mathematics #Mathematics and Applications #Matroid #Minkowski addition #Point processes and geometric inequalities #Political and Social Issues #Polytope #Pure mathematics #Regular polygon
paper · open access · doi:10.1007/978-1-4613-8431-1
published in Graduate texts in mathematics, 1-41 (Springer Nature)
openalex publication_date 1995/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
These lectures on the combinatorics and geometry of 0/1-polytopes are meant as an introduction and invitation. Rather than heading for an extensive survey on 0/1-polytopes I present some interesting aspects of these objects; all of them are related to some quite recent work and progress. 0/1-polytopes have a very simple definition and explicit de& riptions; we can enumerate and analyze small examples explicitly in the computer (e. g. using polymake). However, any intuition that is derived from the analysis of examples in “low dimensions” will miss the true complexity of 0/1-polytopes. Thus, in the following we will study several aspects of the complexity of higher-dimensional 0/1-polytopes: the doubly-exponential number of combinatorial types, the number of facets which can be huge, and the coefficients of defining inequalities which sometimes turn out to be extremely large. Some of the effects and results will be backed by proofs in the course of these lectures; we will also be able to verify some of them on explicit examples, which are accessible as a polymake database. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.