Revlex-initial 0/1-polytopes

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 g nfac ( d , n ) of facets and the minimum average degree g avdeg ( d , n ) of the graph of a d-dimensional 0/1-polytope with n vertices satisfy g nfac ( d , n ) ⩽ 3 d and g avdeg ( 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.