The Numbers of Faces of Polytope Pairs and Unbounded Polyhedra

Abstract

Klee in 1966 proved that every simple d-polyhedron P with v facets has at least v−d+1 vertices. Grünbaum speculated whether this result might be improved upon if one specified both the number of bounded and of unbounded facets of P. In 1974 Klee approached problems of this form from the point of view of pairs of simple polytopes while investigating the efficiency of a proposed algorithm to enumerate the vertices of a simple polytope defined by linear inequalities. In this paper we examine polytopes in a dual fashion to that of Klee, and strengthen and extend some of his results. Specifically, let P be a simplicial d-polytope with v vertices and ∑(P) be the simplicial (d−1)-complex associated with the boundary of P. Suppose, for a given vertex v of P, that we know the numbers of faces of various dimensions of lk∑(P)v. Then we are able to determine tight upper and lower bounds for the possible numbers of faces of all dimensions of P and of ∑(P)\v. As a consequence we resolve some open questions of Klee and settle a conjecture of Björner. © 1981, Academic Press Inc. (London) Limited. All rights reserved.