Maximum Diameter of Abstract Polytopes
STANFORD UNIV CA DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
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.
- Operations Research