Enumeration of 2-level polytopes (Q1741129): Difference between revisions

A polytope is the convex hull of finitely many points in $\mathbb{R}^d$. A hyperplane $H \subset\mathbb{R}^d$ is a supporting hyperplane for the polytope $P$ if $P$ lies entirely on one of the two half spaces defined by $H$. A facet of $P$ is a set $P \cap H$, for some supporting hyperplane $H$, that has dimension 1 smaller than that of $P$, and a vertex of $P$ is a point of the form $P \cap H$ for some supporting hyperplane $H$. \par A polytope $P$ is 2-level if, for any facet supporting hyperplane $H$, the vertices of $P$ that are not on $H$ are all in one specific translate of $H$. (2-level polytopes are also called compressed.) 2-level polytopes have several applications, e.g., in combinatorial optimization and communication complexity. \par The paper under review gives an algorithm to enumerate all 2-level polytopes (up to combinatorial type) in a given dimension, and the authors used their algorithm to build a database of 2-level polytopes of dimension $\le 7$. The algorithm is recursive, using the fact that every facet of a 2-level polytope is again 2-level.