A BOUND ON LOCAL MINIMA OF ARRANGEMENTS THAT IMPLIES THE UPPER BOUND THEOREM

This paper shows that the i-level of an arrangement of hyperplanes in E(d) has at most (i + d - 1/d - 1) local minima. This bound follows from ideas previously used to prove bounds on (less-than-or-equal-to k)-sets. Using linear programming duality, the Upper Bound Theorem is obtained as a corollary, giving yet another proof of this celebrated bound on the number of vertices of a simple polytope in E(d) with n facets.