An $(\aleph_0,k+2)$-Theorem for $k$-Transversals
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917018938114048 |
|---|---|
| author | Keller, Chaya Perles, Micha A. |
| author_facet | Keller, Chaya Perles, Micha A. |
| contents | A family $\mathcal{F}$ of sets satisfies the $(p,q)$-property if among every $p$ members of $\mathcal{F}$, some $q$ can be pierced by a single point. The celebrated $(p,q)$-theorem of Alon and Kleitman asserts that for any $p \geq q \geq d+1$, any family $\mathcal{F}$ of compact convex sets in $\mathbb{R}^d$ that satisfies the $(p,q)$-property can be pierced by a finite number $c(p,q,d)$ of points. A similar theorem with respect to piercing by $(d-1)$-dimensional flats, called $(d-1)$-transversals, was obtained by Alon and Kalai.
In this paper we prove the following result, which can be viewed as an $(\aleph_0,k+2)$-theorem with respect to $k$-transversals: Let $\mathcal{F}$ be an infinite family of closed balls in $\mathbb{R}^d$, and let $0 \leq k < d$. If among every $\aleph_0$ elements of $\mathcal{F}$, some $k+2$ can be pierced by a $k$-dimensional flat, then $\mathcal{F}$ can be pierced by a finite number of $k$-dimensional flats. We derive this result as a corollary of a more general result which proves the same assertion for families of not necessarily convex objects called \emph{near-balls}, to be defined below.
This is the first $(p,q)$-theorem in which the assumption is weakened to an $(\infty,\cdot)$ assumption. Our proofs combine geometric and topological tools. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_02181 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An $(\aleph_0,k+2)$-Theorem for $k$-Transversals Keller, Chaya Perles, Micha A. Combinatorics Computational Geometry 52A35 A family $\mathcal{F}$ of sets satisfies the $(p,q)$-property if among every $p$ members of $\mathcal{F}$, some $q$ can be pierced by a single point. The celebrated $(p,q)$-theorem of Alon and Kleitman asserts that for any $p \geq q \geq d+1$, any family $\mathcal{F}$ of compact convex sets in $\mathbb{R}^d$ that satisfies the $(p,q)$-property can be pierced by a finite number $c(p,q,d)$ of points. A similar theorem with respect to piercing by $(d-1)$-dimensional flats, called $(d-1)$-transversals, was obtained by Alon and Kalai. In this paper we prove the following result, which can be viewed as an $(\aleph_0,k+2)$-theorem with respect to $k$-transversals: Let $\mathcal{F}$ be an infinite family of closed balls in $\mathbb{R}^d$, and let $0 \leq k < d$. If among every $\aleph_0$ elements of $\mathcal{F}$, some $k+2$ can be pierced by a $k$-dimensional flat, then $\mathcal{F}$ can be pierced by a finite number of $k$-dimensional flats. We derive this result as a corollary of a more general result which proves the same assertion for families of not necessarily convex objects called \emph{near-balls}, to be defined below. This is the first $(p,q)$-theorem in which the assumption is weakened to an $(\infty,\cdot)$ assumption. Our proofs combine geometric and topological tools. |
| title | An $(\aleph_0,k+2)$-Theorem for $k$-Transversals |
| topic | Combinatorics Computational Geometry 52A35 |
| url | https://arxiv.org/abs/2306.02181 |