License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.50
URN: urn:nbn:de:0030-drops-160581
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16058/
Go to the corresponding LIPIcs Volume Portal

Keller, Chaya ; Perles, Micha A.

An (ℵ₀,k+2)-Theorem for k-Transversals

pdf-format:
LIPIcs-SoCG-2022-50.pdf (0.8 MB)

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 (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.

BibTeX - Entry

@InProceedings{keller_et_al:LIPIcs.SoCG.2022.50,
  author =	{Keller, Chaya and Perles, Micha A.},
  title =	{{An (\aleph₀,k+2)-Theorem for k-Transversals}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{50:1--50:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16058},
  URN =		{urn:nbn:de:0030-drops-160581},
  doi =		{10.4230/LIPIcs.SoCG.2022.50},
  annote =	{Keywords: convexity, (p,q)-theorem, k-transversal, infinite (p,q)-theorem}
}

Keywords: convexity, (p,q)-theorem, k-transversal, infinite (p,q)-theorem
Collection: 38th International Symposium on Computational Geometry (SoCG 2022)
Issue Date: 2022
Date of publication: 01.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI