Bounds for the collapsibility number of a simplicial complex and non-cover complexes of hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909180663693312 |
|---|---|
| author | Santhanam, Rekha Shukla, Samir Singh, Anurag |
| author_facet | Santhanam, Rekha Shukla, Samir Singh, Anurag |
| contents | 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)}|- γ_i(\mathcal{H})-1$-collapsible, where $γ_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_10607 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Bounds for the collapsibility number of a simplicial complex and non-cover complexes of hypergraphs Santhanam, Rekha Shukla, Samir Singh, Anurag Combinatorics 05C69, 05E45, 52B22, 52A35 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)}|- γ_i(\mathcal{H})-1$-collapsible, where $γ_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. |
| title | Bounds for the collapsibility number of a simplicial complex and non-cover complexes of hypergraphs |
| topic | Combinatorics 05C69, 05E45, 52B22, 52A35 |
| url | https://arxiv.org/abs/2211.10607 |