Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T00:39:41.182Z Has data issue: false hasContentIssue false
  • English
  • Français

On The Number of Faces of a Convex Polytope

Published online by Cambridge University Press:  20 November 2018

David Gale
David Gale*
Affiliation:
Brown University Providence, Rhode Island
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The following problem is as yet unsolved: Given a convex polytope with N vertices in n-space, what is the maximum number of (n — 1)-faces which it can have? Aside from its geometric interest this question arises in connection with solving systems of linear inequalities and linear equations in non-negative variables. The problem is equivalent to asking for the best bound on the number of basic solutions for such problems and hence a bound (though a weak one) for the number of iterations needed in the simplex method for solving linear programmes.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 16 , 1964 , pp. 12 - 17
Copyright
Copyright © Canadian Mathematical Society 1964

References

1. Gale, D., Neighborly and cyclic polytopes , Proc. Symposium on Convex Sets, Seattle, 1961. In press.Google Scholar
2. Klee, V. L., On the number of vertices of a convex polytope, Can. J. Math, (in press).Google Scholar
3. Motzkin, T. S., Comonotone curves and polyhedra, Abstract III, Bull. Amer. Math. Soc, 63 (1957), 35.Google Scholar