Counterexamples to the strong \(d\)-step conjecture for \(d\geq 5\)
type: Item
instance of: scholarly article
title: Counterexamples to the strong \(d\)-step conjecture for \(d\geq 5\)
zbMATH Open document ID: 0899.52007
DOI: 10.1007/PL00009334
published in: Discrete \& Computational Geometry
publication date: 1998-11-16T00:00:00Z
review text: (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.
Mathematics Subject Classification ID: 52B12
Mathematics Subject Classification ID: 52B55
zbMATH DE Number: 1127614
zbMATH Keywords: polytope
zbMATH Keywords: \(d\)-step conjecture
zbMATH Keywords: Dantzig figures
zbMATH Keywords: edge-paths
Wikidata QID: Q122874952
author: Fred B. Holt
author: Victor Klee
reviewed by: Peter McMullen
MaRDI profile type: Publication
full work available at URL: pl00009334
OpenAlex ID: W2037594542
description: scientific article; zbMATH DE number 1127614