DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2022.50

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

Authors: Chaya Keller and Micha A. Perles

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

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.

Cite as

Chaya Keller and Micha A. Perles. An (ℵ₀,k+2)-Theorem for k-Transversals. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.SoCG.2022.50},
  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}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2021.47

No Krasnoselskii Number for General Sets

Authors: Chaya Keller and Micha A. Perles

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract

For a family ℱ of non-empty sets in ℝ^d, the Krasnoselskii number of ℱ is the smallest m such that for any S ∈ ℱ, if every m or fewer points of S are visible from a common point in S, then any finite subset of S is visible from a single point. More than 35 years ago, Peterson asked whether there exists a Krasnoselskii number for general sets in ℝ^d. The best known positive result is Krasnoselskii number 3 for closed sets in the plane, and the best known negative result is that if a Krasnoselskii number for general sets in ℝ^d exists, it cannot be smaller than (d+1)². In this paper we answer Peterson’s question in the negative by showing that there is no Krasnoselskii number for the family of all sets in ℝ². The proof is non-constructive, and uses transfinite induction and the well-ordering theorem. In addition, we consider Krasnoselskii numbers with respect to visibility through polygonal paths of length ≤ n, for which an analogue of Krasnoselskii’s theorem for compact simply connected sets was proved by Magazanik and Perles. We show, by an explicit construction, that for any n ≥ 2, there is no Krasnoselskii number for the family of compact sets in ℝ² with respect to visibility through paths of length ≤ n. (Here the counterexamples are finite unions of line segments.)

Cite as

Chaya Keller and Micha A. Perles. No Krasnoselskii Number for General Sets. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 47:1-47:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{keller_et_al:LIPIcs.SoCG.2021.47,
  author =	{Keller, Chaya and Perles, Micha A.},
  title =	{{No Krasnoselskii Number for General Sets}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{47:1--47:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.47},
  URN =		{urn:nbn:de:0030-drops-138462},
  doi =		{10.4230/LIPIcs.SoCG.2021.47},
  annote =	{Keywords: visibility, Helly-type theorems, Krasnoselskii’s theorem, transfinite induction, well-ordering theorem}
}

Search Results

Documents authored by Perles, Micha A.

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

Abstract

Cite as

No Krasnoselskii Number for General Sets

Abstract

Cite as

Thanks for your feedback!

Could not send message