2023/06/03 by Chaya Keller, Keller, Chaya, Micha A. Perles +1 · 1 citation
Computer Science · Engineering · #52A35 #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2306.02181
openalex publication_date 2023/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
A family F of sets satisfies the (p,q)-property if among every p members of F, some q can be pierced by a single point. The celebrated (p,q)-theorem of Alon and Kleitman asserts that for any p ≥ q ≥ d+1, any family F of compact convex sets in ℝ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 (ℵ0,k+2)-theorem with respect to k-transversals: Let F be an infinite family of closed balls in ℝd, and let 0 ≤ k < d. If among every ℵ0 elements of F, some k+2 can be pierced by a k-dimensional flat, then 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 near-balls, to be defined below. This is the first (p,q)-theorem in which the assumption is weakened to an (∞,⋅) assumption. Our proofs combine geometric and topological tools.