Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes

DOI10.1016/J.JCTB.2021.04.003MaRDI QIDQ2040016zbMATH OpenOpenAlexFDO

Authors Rogers Mathew, Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad

Publication date 6 July 2021

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.07907

zbMATH Keywords

fillingshigh dimensional treeshigh-dimensional combinatoricshypergraphs Hamiltonian cyclessimplicial complexes

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Hypergraphs (05C65) Combinatorial aspects of simplicial complexes (05E45)

Abstract: 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-1choosed$. 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-1choosed-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 $partialF=Z^{d-1}$. We call a $d$-filling Hamiltonian if it is acyclic and of a complete rank, or, equivalently, is of size $n-1choosed$. If a Hamiltonian $d$-cycle $Z$ over $F_2$ contains a $d$-simplex $sigma$, then $Zsetminussigma$ is a a Hamiltonian $d$-filling of $partialsigma$ (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.

Recommendations

• Hamiltonian simple polytopes
• A sharp threshold for spanning 2-spheres in random 2-complexes
• Large simple d-cycles in simplicial complexes
• scientific article; zbMATH DE number 739027
• Hamiltonian submanifolds of regular polytopes

Cites work

• Collapsibility and vanishing of top homology in random simplicial complexes
• Extremal hypercuts and shadows of simplicial complexes
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• Note: Combinatorial Alexander duality -- a short and elementary proof
• On multiplicative \(\lambda\)-approximations and some geometric applications
• On the chromatic number of a simplicial complex
• On the phase transition in random simplicial complexes
• Random Latin squares and 2-dimensional expanders

Cited in

(5)

• On the topology of simplicial complexes related to 3-connected and Hamiltonian graphs
• Extremal hypercuts and shadows of simplicial complexes
• In search of hyperpaths
• A sharp threshold for spanning 2-spheres in random 2-complexes
• Large simple d-cycles in simplicial complexes

This page was built for publication: Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2040016)