Counting d -Step Paths in Extremal Dantzig Figures

Abstract.

The d -step conjecture asserts that every d -polytope P with 2d facets has an edge-path of at most d steps between any two of its vertices. Klee and Walkup showed that to prove the d -step conjecture, it suffices to verify it for all Dantzig figures (P, w ₁ , w ₂ ) , which are simple d -polytopes with 2d facets together with distinguished vertices w ₁ and w ₂ which have no common facet, and to consider only paths between w ₁ and w ₂ . This paper counts the number of d -step paths between w ₁ and w ₂ for certain Dantzig figures (P, w ₁ , w ₂ ) which are extremal in the sense that P has the minimal and maximal vertices possible among such d -polytopes with 2d facets, which are d ² - d + 2 vertices (lower bound theorem) and $2 { \lfloor \frac{3}{2} d - \frac{1}{2} \rfloor \choose \lfloor \frac{d}{2} \rfloor}$ vertices (upper bound theorem), respectively. These Dantzig figures have exactly 2 ^d-1 d -step paths.