##
Tamás Fleiner, Volker Kaibel, and Günter Rote:

#
Upper bounds on the maximal number of facets of 0/1-polytopes

*European Journal of Combinatorics* **21** (2000), 121–130.
doi:10.1006/eujc.1999.0326
###
Abstract

We prove two upper bounds on the number of facets that a *d*-dimensional
0/1-polytope (a polytope whose vertices have coordinates 0 and 1) can have.
The first one is 2(*d*-1)!+2(*d*-1), which is the best one currently
known for small dimensions, while the second one, *O*((*d*-2)!),
is the best bound for large dimensions.
This question was posed by Günter Ziegler in his book *Lectures
on Polytopes* (1995) (exercise 0.15). Our bounds improve the best previously
known bound of *O*(*d*!), which follows from a simple volume
argument due to Imre Bárány. The known lower bounds are exponential,
the current record being 3.6^{d} for large enough *d*.
(Thomas Christof and Gerhard Reinelt 1997). They follow from explicit polytopes
in low dimensions. (Since the paper was published, superexponential lower
bounds were proved by Bárány and Por.)

We also prove bounds for the number of faces of lower dimensions, and
for integral convex polytopes with coordinates between 0 and *k*.

Last update: April 4, 2002.