Intersection patterns in spaces with a forbidden homological minor
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911692781256704 |
|---|---|
| author | Goaoc, Xavier Holmsen, Andreas F. Patáková, Zuzana |
| author_facet | Goaoc, Xavier Holmsen, Andreas F. Patáková, Zuzana |
| contents | In this paper we study generalizations of classical results on intersection patterns of set systems in $\mathbb{R}^d$, such as the fractional Helly theorem or the $(p,q)$-theorem, in the setting of arbitrary triangulable spaces with a forbidden homological minor.
Given a simplicial complex $K$ and an integer $b$, we say that a family $\mathcal{F}$ of subcomplexes of some simplicial complex $X$ is a $(K,b)$-free cover if (i) $K$ is a forbidden homological minor of $X$, and (ii) the $j$th reduced Betti number $\tildeβ_j(\bigcap_{S\in {\mathcal{G}}}S,\mathbb{Z}_2)$ is strictly less than $b$ for all $0\leq j < \dim K$ and all nonempty subfamilies $\mathcal{G}\subseteq \mathcal{F}$.
We show that for every $K$ and $b$, the fractional Helly number of a $(K,b)$-free cover is at most $μ(K)+1$, where $μ(K)$ is the maximum sum of the dimensions of two disjoint faces in $K$. This implies that the assertion of the $(p,q)$-theorem holds for every $p \ge q > μ(K)$ and every $(K,b)$-free cover $\mathcal{F}$. For $b=1$ and a suitable $K$ this recovers the original $(p,q)$-theorem and its generalization to good covers. Interestingly, our results show that that the range of parameters $(p,q)$ for which the $(p,q)$-theorem holds is independent of $b$.
Our proofs use Ramsey-type arguments combined with the notion of stair convexity of Bukh et al. to construct (forbidden) homological minors in certain cubical complexes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2103_09286 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Intersection patterns in spaces with a forbidden homological minor Goaoc, Xavier Holmsen, Andreas F. Patáková, Zuzana Computational Geometry Combinatorics In this paper we study generalizations of classical results on intersection patterns of set systems in $\mathbb{R}^d$, such as the fractional Helly theorem or the $(p,q)$-theorem, in the setting of arbitrary triangulable spaces with a forbidden homological minor. Given a simplicial complex $K$ and an integer $b$, we say that a family $\mathcal{F}$ of subcomplexes of some simplicial complex $X$ is a $(K,b)$-free cover if (i) $K$ is a forbidden homological minor of $X$, and (ii) the $j$th reduced Betti number $\tildeβ_j(\bigcap_{S\in {\mathcal{G}}}S,\mathbb{Z}_2)$ is strictly less than $b$ for all $0\leq j < \dim K$ and all nonempty subfamilies $\mathcal{G}\subseteq \mathcal{F}$. We show that for every $K$ and $b$, the fractional Helly number of a $(K,b)$-free cover is at most $μ(K)+1$, where $μ(K)$ is the maximum sum of the dimensions of two disjoint faces in $K$. This implies that the assertion of the $(p,q)$-theorem holds for every $p \ge q > μ(K)$ and every $(K,b)$-free cover $\mathcal{F}$. For $b=1$ and a suitable $K$ this recovers the original $(p,q)$-theorem and its generalization to good covers. Interestingly, our results show that that the range of parameters $(p,q)$ for which the $(p,q)$-theorem holds is independent of $b$. Our proofs use Ramsey-type arguments combined with the notion of stair convexity of Bukh et al. to construct (forbidden) homological minors in certain cubical complexes. |
| title | Intersection patterns in spaces with a forbidden homological minor |
| topic | Computational Geometry Combinatorics |
| url | https://arxiv.org/abs/2103.09286 |