Revlex-initial 0/1-polytopes (Q2497967)

The authors of this article examine certain polytopes whose vertices are a subset of the vertices of the unit cube, specifically, the vertices (elements of \(\{0,1\}^d\)) consist of all binary representations of numbers \(0,1,\dots,n-1\) for some \(n\). Such polytopes are called revlex-initial 0/1-polytopes. The work is motivated by experiments by the authors with certain convex hull algorithms. The algorithms were more efficient than the authors expected, and they found that intermediate steps of the algorithms tended to be working with polytopes which were similar to revlex-initial 0/1-polytopes. The authors charaterise the facets of revlex-initial 0/1-polytopes, and find systems of linear inequalities that yield the polytopes. The vertex-edge graphs of the polytopes are described, and the authors calculate the number of edges and average degree of the graphs, showing them to be surprisingly sparse. They also show that the edge-expansion is at least one, supporting a conjecture by Mihail and Vazirani. Some graphs are given showing the quantities calculated for wide ranges of \(n\), and other graphs given showing the computational efficiency of the convex hull algorithms applied to random 0/1-polytopes.