Bounding Radon numbers via Betti numbers

Abstract

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 $\epsilon$-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.

22 pages; Ramsey part significantly expanded

References in corpus (2)

• Nerves, minors, and piercing numbers
• The ${\mathbb{Z}}_2$-genus of Kuratowski minors