Maximal nonrevisiting paths in simple polytopes

AbstractThirty years ago the connection was established between the presence of nonrevisiting paths in a d-polytope and the polytope's edge-diameter. The operation of wedging was used to establish the equivalence of the nonrevisiting conjecture and the Hirsch conjecture. Recently, wedging and other operations have again provided the best available results related to the Hirsch conjecture. In this paper we analyze the effect of wedging and these other operations on the number of maximal nonrevisiting paths in simple polytopes. Two results follow from this accounting. First, following up on the strong d-step conjecture, we establish a new upper bound for the minimum number of paths of length d connecting estranged vertices in a d-polytope with 2d facets. Second, we observe that not only do the operations considered fail to eliminate nonrevisiting paths, these operations do not even reduce the number of such paths