Face nonrevisiting conjecture for lattice Hasse diagrams of simple polytopes
Face nonrevisiting conjecture for lattice Hasse diagrams of simple polytopes
Let be a simple polytope and let be a generic cost vector such that is the Hasse diagram of a lattice. A directed path in is said to revisit a face if it leaves that face and later returns to it. Face nonrevisiting conjecture. Directed paths in never revisit any face they have left. Equivalently, if is a directed path and and both lie in a face , then for . This property would imply an upper bound of on the length of directed paths, where is the dimension of and is its number of facets. The conjecture proposes a sufficient condition for controlling directed path lengths and is motivated by implications for the diameter of polytope graphs and the efficiency of the simplex method; the supplied text gives no resolution.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Patricia Hersh, “Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology”, arXiv:1802.04342 (2023).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.