Upper bound theorem

Remarks

The theorem was proved by Peter McMullen in 1970, after Theodore Motzkin had conjectured it. Proof idea: a small perturbation of the vertices makes $P$ simplicial without lowering any $f_i$, so one may assume $P$ simplicial. Then one passes to the h-vector of the boundary, uses the Dehn–Sommerville equations $h_i = h_{d-i}$, and proves $h_i \le \binom{n - d + i - 1}{i}$ for $i \le d/2$ with a shelling of the boundary. Cyclic polytopes attain all these bounds, because they are neighborly.

The number of facets of $C(n, d)$ is $$f_{d-1}(C(n,d)) = \frac{n}{n - m} \binom{n - m}{m} \text{ if } d = 2m, \qquad 2 \binom{n - m - 1}{m} \text{ if } d = 2m + 1.$$ For $d = 3$ this gives $2n - 4$, the number of triangles of any simplicial $3$-polytope with $n$ vertices. For $d = 4$ and $n = 8$ it gives $8 \cdot 15 / 6 = 20$ facets.

By polar polytope duality, the theorem also bounds the number of vertices of a $d$-polytope with $n$ facets.

Going deeper

For a student

In the dual form, a polytope with $n$ facets in dimension $d$ has at most about $n^{\floor{d/2}}$ vertices. This bounds the number of vertices that the simplex method or a vertex enumeration algorithm may meet, and the size of convex hulls in computational geometry. The theorem was extended to simplicial spheres by Richard Stanley using commutative algebra. Its lower-bound partner, for simplicial polytopes, is the lower bound theorem, and both are contained in the g-theorem.