Face nonrevisiting conjecture for lattice Hasse diagrams of simple polytopes

From papers

Let PP be a simple polytope and let c{\bf c} be a generic cost vector such that G(P,c)G(P, {\bf c}) is the Hasse diagram of a lattice. A directed path in G(P,c)G(P,{\bf c}) is said to revisit a face if it leaves that face and later returns to it. Face nonrevisiting conjecture. Directed paths in G(P,c)G(P, {\bf c}) never revisit any face they have left. Equivalently, if v1v2vkv_1\rightarrow v_2\rightarrow \cdots \rightarrow v_k is a directed path and v1v_1 and vkv_k both lie in a face FF, then viFv_i\in F for 1ik1\le i\le k. This property would imply an upper bound of ndn-d on the length of directed paths, where dd is the dimension of PP and nn 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

No solutions have been posted yet.