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


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.6d 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.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)
other papers about this subject
Last update: April 4, 2002.