Next: How hard is it
Up: Convex Polyhedron
Previous: How many facets does
How many facets can a 0-1 polytope with vertices in
Let denote the maximum number of facets of a
0-1 polytope in .
The question such as ``is this function bounded by an exponential in ?''
was open just until recently. The negative answer was given by
Bárány and Pór who proved the superexponential behavior
This is a recent breakthrough in the theory of 0-1 polytopes.
(Bárány and Pór [BP00
There is a positive constant