Revlex-initial 0/1-polytopes

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

Authors Rafael Gillmann, Volker Kaibel

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

zbMATH Keywords

graphfacetsedges0/1 polytopeedge expansionconvex hull algorithmextremal f-vector

Mathematics Subject Classification ID

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

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.

Recommendations

• 0/1-Polytopes. Typical and extremal properties
• scientific article; zbMATH DE number 2196285
• On the Maximal Number of Facets of 0/1 Polytopes
• Extremal properties of 0/1-polytopes
• Lower bound for the maximal number of facets of a 0/1 polytope

Cites work

• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 1538119 (Why is no real title available?)
• scientific article; zbMATH DE number 1538123 (Why is no real title available?)
• scientific article; zbMATH DE number 2196285 (Why is no real title available?)
• Decompositions of Rational Convex Polytopes
• Lectures on Polytopes
• Lower bound for the maximal number of facets of a 0/1 polytope
• On 0-1 polytopes with many facets
• On the expansion of combinatorial polytopes
• Simple 0/1-polytopes
• Upper bounds on the maximal number of facets of 0/1-polytopes

Cited in

(9)

• Knapsack polytopes: a survey
• Convex hulls of superincreasing knapsacks and lexicographic orderings
• On Dantzig figures from graded lexicographic orders
• Convex hull characterizations of lexicographic orderings
• scientific article; zbMATH DE number 2196285 (Why is no real title available?)
• Equivalence classes of full-dimensional 0/1-polytopes with many vertices
• 0/1-Polytopes. Typical and extremal properties
• Lexicographical polytopes
• Expansion of random 0/1 polytopes

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)