Keller, Chaya ;
Perles, Micha A.
An (ℵ₀,k+2)Theorem for kTransversals
Abstract
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 (d1)dimensional flats, called (d1)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 ktransversals: 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 kdimensional flat, then ℱ can be pierced by a finite number of kdimensional flats.
This is the first (p,q)theorem in which the assumption is weakened to an (∞,⋅) assumption. Our proofs combine geometric and topological tools.
BibTeX  Entry
@InProceedings{keller_et_al:LIPIcs.SoCG.2022.50,
author = {Keller, Chaya and Perles, Micha A.},
title = {{An (\aleph₀,k+2)Theorem for kTransversals}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {50:150:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16058},
URN = {urn:nbn:de:0030drops160581},
doi = {10.4230/LIPIcs.SoCG.2022.50},
annote = {Keywords: convexity, (p,q)theorem, ktransversal, infinite (p,q)theorem}
}
01.06.2022
Keywords: 

convexity, (p,q)theorem, ktransversal, infinite (p,q)theorem 
Seminar: 

38th International Symposium on Computational Geometry (SoCG 2022)

Issue date: 

2022 
Date of publication: 

01.06.2022 