Revlex-initial 0/1-polytopes

DOI10.1016/J.JCTA.2005.07.010MaRDI QIDQ2497967zbMATH OpenOpenAlexFDO

Publication date 4 August 2006

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0412028

0/1 polytope convex hull algorithm edge expansion edges extremal f-vector facets graph

Convex sets without dimension restrictions (aspects of convex geometry) (52A05) (n)-dimensional polytopes (52B11) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial complexity of geometric structures (52C45) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: We introduce revlex-initial 0/1-polytopes as the convex hulls of reverse-lexicographically initial subsets of 0/1-vectors. These polytopes are special knapsack-polytopes. It turns out that they have remarkable extremal properties. In particular, we use these polytopes in order to prove that the minimum numbers f(d, n) of facets and the minimum average degree a(d, n) of the graph of a d-dimensional 0/1-polytope with n vertices satisfy f(d, n) <= 3d and a(d, n) <= d + 4. We furthermore show that, despite the sparsity of their graphs, revlex-initial 0/1-polytopes satisfy a conjecture due to Mihail and Vazirani, claiming that the graphs of 0/1-polytopes have edge-expansion at least one.

Review text

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.

Recommendations

Cites work

Cited in

(10)

Describes a project that uses

Uses Software

01poly

This page was built for publication: Revlex-initial 0/1-polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2497967)