TY - JOUR
AU - Lagarias, J. C.
AU - Prabhu, N.
PY - 1998
DA - 1998/01/01
TI - Counting d -Step Paths in Extremal Dantzig Figures
JO - Discrete & Computational Geometry
SP - 19
EP - 31
VL - 19
IS - 1
AB - 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, w1,w2) , which are simple d -polytopes with 2d facets together with distinguished vertices w1and w2which have no common facet, and to consider only paths between w1and w2. This paper counts the number of d -step paths between w1and w2for certain Dantzig figures (P, w1, w2) which are extremal in the sense that P has the minimal and maximal vertices possible among such d -polytopes with 2d facets, which are d2- 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 2d-1d -step paths.
SN - 1432-0444
UR - https://doi.org/10.1007/PL00009333
DO - 10.1007/PL00009333
ID - Lagarias1998
ER -