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.
References
Primary source
Patricia Hersh, “Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology”, arXiv:1802.04342 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.