Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes

Abstract We introduce and study a d -dimensional generalization of graph Hamiltonian cycles . These are the Hamiltonian d-dimensional cycles in K n d (the complete simplicial d-complex over a vertex set of size n). Hamiltonian d-cycles are the simple d-cycles of a complete rank, or, equivalently, of size 1 + ( n − 1 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 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 ∈ K n d , F is its d-filling if ∂ 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 d ) . If a Hamiltonian d-cycle Z over F 2 contains a d-simplex σ, then Z ∖ σ is a Hamiltonian d-filling of ∂σ (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.