next up previous contents
Next: How hard is it Up: Convex Polyhedron Previous: How many facets does   Contents

How many facets can a 0-1 polytope with $ n$ vertices in $ R^d$ have?

Let $ f(d)$ denote the maximum number of facets of a 0-1 polytope in $ R^d$. The question such as ``is this function bounded by an exponential in $ d$?'' was open just until recently. The negative answer was given by Bárány and Pór who proved the superexponential behavior of $ f(d)$.

Theorem 6 (Bárány and Pór [BP00])   There is a positive constant $ c$ such that

$\displaystyle f(d) > \left ( \frac{c\;d}{\log d} \right )^\frac{d}{4}.$ (2)

This is a recent breakthrough in the theory of 0-1 polytopes.

Komei Fukuda 2004-08-26