Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes

Mathew, R. and Newman, I. and Rabinovich, Y. and Rajendraprasad, D. (2021) Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes. Journal of Combinatorial Theory. Series B, 150. pp. 119-143. ISSN 00958956

Full text not available from this repository. (Request a copy)


We introduce and study a d-dimensional generalization of graph Hamiltonian cycles. These are the Hamiltonian d-dimensional cycles in Knd (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−1d). The discussion is restricted to the fields F2 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−1d)−O(nd−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 Zd−1∈Knd, F is its d-filling if ∂F=Zd−1. We call a d-filling Hamiltonian if it is acyclic and of a complete rank, or, equivalently, is of size (n−1d). If a Hamiltonian d-cycle Z over F2 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. © 2021 Elsevier Inc.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Mathew, Rogershttps://orcid.org/0000-0003-4536-1136
Item Type: Article
Uncontrolled Keywords: Fillings, High dimensional trees, High-dimensional combinatorics, Hypergraphs Hamiltonian cycles, Simplicial complexes
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Mrs Haseena VKKM
Date Deposited: 13 Apr 2022 05:06
Last Modified: 13 Apr 2022 05:06
URI: http://raiith.iith.ac.in/id/eprint/9204
Publisher URL: https://www.sciencedirect.com/science/article/abs/...
OA policy: https://v2.sherpa.ac.uk/id/publication/11367
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9204 Statistics for this ePrint Item