Maximum Diameter of Abstract Polytopes
Abstract
Walkup and Klee studied the diameter of ordinary convex polytopes which is defined as the smallest integer k such that all pairs of vertices can be joined by a path of k or less neighboring vertices. The well known d-step (or Hirsch) conjecture for d dimensional polytopes with n facets states that the maximum diameter is n - d. Walkup and Klee showed the conjecture as correct for all n - d < or = 5. In an effort to extend the results, the authors of the paper abstract (in the form of three simple axioms) some of the combinatorial properties of ordinary polytopes and show that these are sufficient to establish the maximum diameter is n - d for all n - d < or = 5 and a variety of bounds for other values of n and d. Abstract polytopes are a special class of pseudo manifolds. The results provide insight into the number of iterations required to solve a linear program using the simplex method.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1971
- Accession Number
- AD0737652
Entities
People
- George Bernard Dantzig
- Ilan Adler
Organizations
- Stanford University