Simple 0/1-polytopes

DOI10.1006/EUJC.1999.0328MaRDI QIDQ1964656zbMATH OpenOpenAlexFDO

Authors Volker Kaibel, Martin Wolff

Publication date 4 January 2001

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/5b1edc117aadb3949f82ffb66913b9a5a972a76c

zbMATH Keywords

0/1-polytopecartesian product of 0/1-simpliceshypercubestar-partition

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Combinatorial optimization (90C27)

Review text

A polytope is said to be a 0/1-polytope if it has only vertices with 0/1-coordinates. A \(d\)-dimensional polytope is said to be simple if every of its vertices lies in \(d\)-facets. The authors show that the set of all simple 0/1-polytopes is very small. More precisely, they prove that every simple 0/1-polytope is the cartesian product of some 0/1-simplices.

Recommendations

• scientific article; zbMATH DE number 1538119
• Upper bounds on the maximal number of facets of 0/1-polytopes
• scientific article; zbMATH DE number 1538123
• On the Maximal Number of Facets of 0/1 Polytopes
• Representing simple d-dimensional polytopes by d polynomials

Cites work

• Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
• Extremal properties of 0/1-polytopes
• scientific article; zbMATH DE number 4201996 (Why is no real title available?)
• Lectures on Polytopes
• The Hirsch conjecture is true for (0,1)-polytopes

Cited in

(16)

• Seminormality, canonical modules, and regularity of cut polytopes
• Polytopes close to being simple
• On descriptions of products of simplices
• Revlex-initial 0/1-polytopes
• Existence of unimodular triangulations -- positive results
• Normal 0-1 polytopes
• The characteristic imset polytope of Bayesian networks with ordered nodes
• A lexicographic semiorder polytope and probabilistic representations of choice
• scientific article; zbMATH DE number 1538119 (Why is no real title available?)
• scientific article; zbMATH DE number 1538123 (Why is no real title available?)
• DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES
• Torsionfreeness for divisor class groups of toric rings of integral polytopes
• Toric rings of (0, 1)-polytopes with small rank
• Monogamy of entanglement between cones
• Projectivities in simplicial complexes and colorings of simple polytopes
• On permutation polytopes

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

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