Counterexamples to the strong \(d\)-step conjecture for \(d\geq 5\) (Q1380785): Difference between revisions

(Refer to the previous review [\textit{J. C. Lagarias} and \textit{N. Prabhu}, ibid., 19-31 (1998)] for the basic definitions.) In this paper, the authors show that the \(d\)-step conjecture in the strong form proposed by \textit{J. C. Lagarias}, \textit{N. Prabhu} and \textit{J. A. Reeds} [Discrete Comput. Geom. 19, No. 1, 53-82 (1997)] is true for \(d\leq 4\), but false for \(d\geq 5\). In fact, when \(d\geq 5\), there exist Dantzig figures which have only \(3\cdot 2^{d-3}\) edge-paths between the distinguished vertices. This still leaves open the possibility that there may be an exponential number (perhaps even \(c\cdot 2^d\)) of such edge-paths on a general Dantzig figure.