    Next: What is convex hull? Up: Convex Polyhedron Previous: What is 0-1 polytope?   Contents

## What is the best upper bound of the numbers of -dimensional faces of a -polytope with vertices?

Let denote the number of -faces of a -polytope , for .

The exact upper bound for in terms of and . is known, thanks to McMullen's upper bound theorem.

The convex hull of distinct points on the moment curve in is known as a cyclic polytope. It is known that its combinatorial structure (i.e. its face lattice, see Section 2.3) is uniquely determined by and . Thus we often write to denote any such cyclic -polytope with vertices.

McMullen's Upper Bound Theorem shows that the maximum of is attained by the cyclic polytopes.

Theorem 2 (Upper Bound Theorem)   For any -polytope with vertices, holds.

The number of -faces of a cyclic polytope can be explicitely given and thus one can evaluate the order of the upper bound in terms of and .

Theorem 3   For and , where . In particular, (1)

For example, The upper bound theorem can be written in dual form which gives, for example, the maximum number of vertices in a -polytope with facets.

Theorem 4 (Upper Bound Theorem in Dual Form)   For any -polytope with facets, holds.

The original proof of the Upper Bound Theorem is in [McM70,MS71]. There are different variations, see [Kal97,Mul94,Zie94].    Next: What is convex hull? Up: Convex Polyhedron Previous: What is 0-1 polytope?   Contents
Komei Fukuda 2004-08-26