Name
Title | ||
|---|---|---|
Counting <Emphasis Type="Italic">d</Emphasis> -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 1 ,w 2 ) , which are simple d -polytopes with 2d facets together with distinguished vertices w 1 and w 2 which have no common facet, and to consider only paths between w 1 and w 2 . This paper counts the number of d -step paths between w 1 and w 2 for certain Dantzig figures (P, w 1 , w 2 ) 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 2 - 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. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/PL00009333 | Discrete & Computational Geometry |
Keywords | Field | DocType |
Distinguished Vertex, Common Facet, Maximal Vertex, Step Path, Dantzig Figure | Discrete mathematics,Combinatorics,Vertex (geometry),Upper and lower bounds,Polytope,Facet (geometry),Conjecture,Mathematics,Upper bound theorem | Journal |
Volume | Issue | ISSN |
19 | 1 | 1432-0444 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. C. Lagarias | 1 | 563 | 235.61 |
| Nagabhushana Prabhu | 2 | 22 | 7.43 |