Face nonrevisiting conjecture for lattice Hasse diagrams of simple polytopes

About 8 years old · traced to

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 v1→v2→⋯→vkv_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 vi∈Fv_i\in F for 1≤i≤k1\le i\le k. This property would imply an upper bound of n−dn-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.

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

Never refreshed

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.