Bounding Radon numbers via Betti numbers
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2019
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910724525129728 |
|---|---|
| author | Patáková, Zuzana |
| author_facet | Patáková, Zuzana |
| contents | We prove general topological Radon-type theorems for sets in $\mathbb R^d$ or on a surface. Combined with a recent result of Holmsen and Lee, we also obtain fractional Helly theorem, and consequently the existence of weak $\varepsilon$-nets as well as a $(p,q)$-theorem for those sets.
More precisely, given a family $\mathcal F$ of subsets of $\mathbb R^d$, we will measure the homological complexity of $\mathcal F$ by the supremum of the first $\lceil d/2\rceil$ reduced Betti numbers of $\bigcap \mathcal G$ over all nonempty $\mathcal G \subseteq \mathcal F$. We show that if $\mathcal F$ has homological complexity at most $b$, the Radon number of $\mathcal F$ is bounded in terms of $b$ and $d$. In case that $\mathcal F$ lives on a surface and the number of connected components of $\bigcap \mathcal G$ is at most $b$ for any nonempty $\mathcal G \subseteq \mathcal F$, then the Radon number of $\mathcal F$ is bounded by a function depending only on $b$ and the surface itself.
For surfaces, if we moreover assume the sets in $\mathcal F$ are open, we show that the fractional Helly number of $\mathcal F$ is linear in $b$. The improvement is based on a recent result of the author and Kalai. Specifically, for $b=1$ we get that the fractional Helly number is at most three, which is optimal. This case further leads to solving a conjecture of Holmsen, Kim, and Lee about an existence of a $(p,q)$-theorem for open subsets of a surface. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1908_01677 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Bounding Radon numbers via Betti numbers Patáková, Zuzana Combinatorics We prove general topological Radon-type theorems for sets in $\mathbb R^d$ or on a surface. Combined with a recent result of Holmsen and Lee, we also obtain fractional Helly theorem, and consequently the existence of weak $\varepsilon$-nets as well as a $(p,q)$-theorem for those sets. More precisely, given a family $\mathcal F$ of subsets of $\mathbb R^d$, we will measure the homological complexity of $\mathcal F$ by the supremum of the first $\lceil d/2\rceil$ reduced Betti numbers of $\bigcap \mathcal G$ over all nonempty $\mathcal G \subseteq \mathcal F$. We show that if $\mathcal F$ has homological complexity at most $b$, the Radon number of $\mathcal F$ is bounded in terms of $b$ and $d$. In case that $\mathcal F$ lives on a surface and the number of connected components of $\bigcap \mathcal G$ is at most $b$ for any nonempty $\mathcal G \subseteq \mathcal F$, then the Radon number of $\mathcal F$ is bounded by a function depending only on $b$ and the surface itself. For surfaces, if we moreover assume the sets in $\mathcal F$ are open, we show that the fractional Helly number of $\mathcal F$ is linear in $b$. The improvement is based on a recent result of the author and Kalai. Specifically, for $b=1$ we get that the fractional Helly number is at most three, which is optimal. This case further leads to solving a conjecture of Holmsen, Kim, and Lee about an existence of a $(p,q)$-theorem for open subsets of a surface. |
| title | Bounding Radon numbers via Betti numbers |
| topic | Combinatorics |
| url | https://arxiv.org/abs/1908.01677 |