Revlex-initial 0/1-polytopes

DOI10.1016/J.JCTA.2005.07.010zbMATH Open1099.52002arXivmath/0412028OpenAlexW2091068541MaRDI QIDQ2497967FDOQ2497967

Authors: Rafael Gillmann, Volker Kaibel 

Publication date: 4 August 2006

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Decompositions of Rational Convex Polytopes
• Lectures on Polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bound for the maximal number of facets of a 0/1 polytope
• On 0-1 polytopes with many facets
• Upper bounds on the maximal number of facets of 0/1-polytopes
• Simple 0/1-polytopes
• On the expansion of combinatorial polytopes

Cited In (9)

• Knapsack polytopes: a survey
• Convex hulls of superincreasing knapsacks and lexicographic orderings
• On Dantzig figures from graded lexicographic orders
• Title not available (Why is that?)
• Convex hull characterizations of lexicographic orderings
• 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

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)