2026-07-22T13:39:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16058 2024-03-06T10:56:51Z ddc:004 open_access

An (ℵ₀,k+2)-Theorem for k-Transversals Keller, Chaya Perles, Micha A. convexity (p,q)-theorem k-transversal infinite (p,q)-theorem A family ℱ of sets satisfies the (p,q)-property if among every p members of ℱ, 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 ℱ 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 (ℵ₀,k+2)-theorem with respect to k-transversals: Let ℱ be an infinite family of sets in ℝ^d such that each A ∈ ℱ contains a ball of radius r and is contained in a ball of radius R, and let 0 ≤ k < d. If among every ℵ₀ elements of ℱ, some k+2 can be pierced by a k-dimensional flat, then ℱ can be pierced by a finite number of k-dimensional flats. This is the first (p,q)-theorem in which the assumption is weakened to an (∞,⋅) assumption. Our proofs combine geometric and topological tools. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chaya Keller and Micha A. Perles 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.50 urn:nbn:de:0030-drops-160581 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.50 eng https://creativecommons.org/licenses/by/4.0/legalcode