2022/11/19 by Rekha Santhanam, Santhanam, Rekha, Samir Shukla +3
Computer Science · Mathematics · #05C69 #05E45 #52A35 #52B22 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Commutative Algebra and Its Applications #FOS: Mathematics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2211.10607
openalex publication_date 2022/11/19 · openalex created_date 2022/11/29 · openalex updated_date 2026/07/28
The collapsibility number of simplicial complexes was introduced by Wegner in order to understand the intersection patterns of convex sets. This number also plays an important role in a variety of Helly type results. We show that the non-cover complex of a hypergraph H is |V(H)|- γi(H)-1-collapsible, where γi(H) is the generalization of independence domination number of a graph to hypergraph. This extends the result of Choi, Kim and Park from graphs to hypergraphs. Moreover, the upper bound in terms of strong independence domination number given by Kim and Kim for the Leray number of the non-cover complex of a hypergraph can be obtained as a special case of our result. In general, there can be a large gap between the collapsibility number of a complex and its well-known upper bounds. In this article, we construct a sequence of upper bounds Mk(X) for the collapsibility number of a simplicial complex X, which lie in this gap. We also show that the bound given by Mk is tight if the underlying complex is k-vertex decomposable.