Jump to content

0/1-polytope

From Wikipedia, the free encyclopedia

A 0/1-polytope is a convex polytope generated by the convex hull of a subset of d coordinates value 0 or 1, {0,1}d.[1] The full domain is the unit hypercube with cut hyperplanes passing through these coordinates.[2] A d-polytope requires at least d + 1 vertices, and can't be all in the same hyperplanes.

n-simplex polytopes for example can be generated n + 1 vertices, using the origin, and one vertex along each primary axis, (1,0....), etc. Every simple 0/1-polytope is a Cartesian product of 0/1 simplexes.[3]

References

[edit]
  1. ^ Ziegler, Günter M. (2000). "Lectures on 0/1-polytopes". Polytopes—combinatorics and computation (Oberwolfach, 1997). DMV Sem. Vol. 29. Basel: Birkhäuser. pp. 1–41. ISBN 3-7643-6351-7. MR 1785291.
  2. ^ Grünbaum, Branko (2003). "4.9. Additional notes and comments". Convex Polytopes. Springer. p. 69a.
  3. ^ Kaibel, Volker; Wolff, Martin (2000). "Simple 0/1-polytopes". European Journal of Combinatorics. 21 (1): 139–144. doi:10.1006/eujc.1999.0328. MR 1737334.