Counting \(d\)-step paths in extremal Dantzig figures (Q1380783)

A Dantzig figure is a simple \(d\)-polytope \(P\) with \(2d\) vertices, of which \(d\) contain one distinguished vertex \(x\), and the rest the other distinguished vertex \(y\). The \(d\)-step conjecture claims that between \(x\) and \(y\) there always exists a path of just \(d\) edges of \(P\). In recent years, opinion has tended towards a disbelief in the \(d\)-step conjecture. However, the present authors and \textit{J. A. Reeds} [Discrete Comput. Geom. 18, No. 1, 53-82 (1997)] have suggested that not only might the \(d\)-step conjecture be true, but that it could hold in a strong way, in that between \(x\) and \(y\) there would exist at least \(2^{d-1}\) edge-paths of length \(d\). However, \textit{F. Holt} and \textit{V. Klee} [Discrete Comput. Geom. 19, No. 1, 33-46 (1998)] (see the next review) have disproved this in general. Here, the authors establish that the conjecture is valid for two special kinds of Dantzig figure, namely those which are dual to a stacked polytope (a unique type) or a cycle polytope (with a particular choice of \(x\) and \(y\)); these have the minimal and maximal possible numbers of vertices.