On the Number of Vertices of a Convex Polytope

Abstract

As is well known, the theory of linear inequalities is closely related to the study of convex polytopes. If the bounded subset P of euclidean d -space has a non-empty interior and is determined by i linear inequalities in d variables, then P is a d -dimensional convex polytope (here called a d-polytope ) which may have as many as i faces of dimension d — 1, and the vertices of this polytope are exactly the basic solutions of the system of inequalities. Thus, to obtain an upper estimate of the size of the computation problem which must be faced in solving a system of linear inequalities, it suffices to find an upper bound for the number f 0 ( P ) of vertices of a d -polytope P which has a given number f d -1 ( P ) of ( d — l)-faces. A weak bound of this sort was found by Saaty (14), and several authors have posed the problem of finding a sharp estimate.