math.CO
Hamiltonian and Pseudo Hamiltonian Cycles and Fillings In Simplicial Complexes. We introduce and study a d dimensional generalization of Hamiltonian cycles in graphs the Hamiltonian d cycles in K n d (the complete simplicial d complex over a vertex set of size n ). Those are the simple d cycles of a complete rank, or, equivalently, of size 1 n 1 choose d . The discussion is restricted to the fields F 2 and Q . For d 2 , we characterize the n 's for which Hamiltonian 2 cycles exist. For d 3 it is shown that Hamiltonian 3 cycles exist for infinitely many n 's. In general, it is shown that there always exist simple d cycles of size n 1 choose d O(n d 3 ) . All the above results are constructive. Our approach naturally extends to (and in fact, involves) d fillings, generalizing the notion of T joins in graphs. Given a (d 1) cycle Z d 1 in K n d , F is its d filling if partial F Z d 1 . We call a d filling Hamiltonian if it is acyclic and of a complete rank, or, equivalently, is of size n 1 choose d . If a Hamiltonian d cycle Z over F 2 contains a d simplex sigma , then Z setminus sigma is a a Hamiltonian d filling of partial sigma (a closely related fact is also true for cycles over Q ). Thus, the two notions are closely related. Most of the above results about Hamiltonian d cycles hold for Hamiltonian d fillings as well.