Facet-Hamiltonicity

We consider facet-Hamiltonian cycles of polytopes, defined as cycles in their skeleton such that every facet is visited exactly once. These cycles can be understood as optimal watchman routes that guard the facets of a polytope. We consider the existence of such cycles for a variety of polytopes, the facets of which have a natural combinatorial interpretation. In particular, we prove the following results:

• Every permutahedron has a facet-Hamiltonian cycle. These cycles consist of circular sequences of permutations of n elements, where two successive permutations differ by a single adjacent transposition, and such that every subset of [n] appears as a prefix in a contiguous subsequence. With these cycles we associate what we call rhombic strips which encode interleaved Gray codes of the Boolean lattice, one Gray code for each rank. These rhombic strips correspond to simple Venn diagrams.

• Every generalized associahedron has a facet-Hamiltonian cycle. This generalizes the so-called rainbow cycles of Felsner, Kleist, Mütze, and Sering (SIDMA 2020) to associahedra of any finite type. For types A, B/C, and D, facets have natural interpretations in terms of arcs in triangulations, and the facet-Hamiltonian cycles yield sequences of triangulations, where two successive triangulations differ by a single adjacent flip, and in which every arc appears and disappears exactly once. We relate the constructions to the Conway-Coxeter friezes and the bipartite belts of finite type cluster algebras.

• Graph associahedra of wheels, fans, and complete split graphs have facet-Hamiltonian cycles. For associahedra of complete bipartite graphs and caterpillars, we construct facet-Hamiltonian paths. Here the facets correspond to tubes, or connected induced subgraphs, and we obtain a sequence of elimination trees on those graphs such that every tube appears as a subtree exactly once. The construction involves new insights on the combinatorics of graph tubings.

We also consider the computational complexity of deciding whether a given polytope has a facet-Hamiltonian cycle and show that the problem is NP-complete, even when restricted to simple 3-dimensional polytopes.