Polytope Pairs and Their Relationship to Linear Programming.
WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS
Pagination or Media Count:
An important development in the theory of convex polytopes was the determination by Barnette and McMullen of the minimum and maximum of vP number of vertices of P as P ranges over all simple d-polytopes with n facets. Their results are here extended to certain pairs consisting of a polytope and one of its facets. Corollaries of our main results are the determination of the minimum and maximum of vP as P ranges over all simple d-polyhedra with u unbounded and n - u bounded facets, and of the minimum and maximum of vP not FvF as P,F ranges over all pairs consisting of a simple d-polytope P with n facets and a facet F intersecting all other facets of P. Such pairs, called Kirkman pairs of class d,n, are related to several aspects of linear programming, including a recent algorithm of Mattheiss for finding all vertices of a polytope defined by a system of linear inequalities. Author
- Operations Research