Maximal nonrevisiting paths in simple polytopes
Let \(\Delta(d,n)\) denote the maximum edge-diameter among all simple \(d\)-dimensional polytopes with \(n\) facets. The Hirsch conjecture states that \(\Delta(d,n)\leq n-d\) for all \(n> d\geq 2\). The nonrevisiting path conjecture states that in any polytope, every pair of vertices is connected by a nonrevisiting path. These two conjectures have been shown to be equivalent. Recently operations on polytopes (such as wedging) have been used to get the best available results related to the Hirsch conjecture. The author uses the same operations to study the maximal number of nonrevisiting paths in simple polytopes.
scientific article; zbMATH DE number 1895988