References & Citations
Mathematics > Combinatorics
Title: Bounds for the collapsibility number of a simplicial complex and non-cover complexes of hypergraphs
(Submitted on 19 Nov 2022 (v1), last revised 25 Apr 2024 (this version, v3))
Abstract: 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 $\mathcal{H}$ is $|V(\mathcal{H)}|- \gamma_i(\mathcal{H})-1$-collapsible, where $\gamma_i(\mathcal{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 $\mathcal{M}_k(X)$ for the collapsibility number of a simplicial complex $X$, which lie in this gap. We also show that the bound given by $\mathcal{M}_k$ is tight if the underlying complex is $k$-vertex decomposable.
Submission history
From: Samir Shukla [view email][v1] Sat, 19 Nov 2022 07:35:22 GMT (14kb)
[v2] Tue, 23 Apr 2024 08:30:12 GMT (18kb)
[v3] Thu, 25 Apr 2024 13:05:38 GMT (18kb)
Link back to: arXiv, form interface, contact.