Bounding radon number via Betti numbers

Z. Patakova, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 61:1-61:13.

Download
OA 2020_LIPIcsSoCG_Patakova_61.pdf 645.42 KB

Conference Paper | Published | English

Scopus indexed
Department
Series Title
LIPIcs
Abstract
We prove general topological Radon-type theorems for sets in ℝ^d, smooth real manifolds or finite dimensional simplicial complexes. Combined with a recent result of Holmsen and Lee, it gives fractional Helly theorem, and consequently the existence of weak ε-nets as well as a (p,q)-theorem. More precisely: Let X be either ℝ^d, smooth real d-manifold, or a finite d-dimensional simplicial complex. Then if F is a finite, intersection-closed family of sets in X such that the ith reduced Betti number (with ℤ₂ coefficients) of any set in F is at most b for every non-negative integer i less or equal to k, then the Radon number of F is bounded in terms of b and X. Here k is the smallest integer larger or equal to d/2 - 1 if X = ℝ^d; k=d-1 if X is a smooth real d-manifold and not a surface, k=0 if X is a surface and k=d if X is a d-dimensional simplicial complex. Using the recent result of the author and Kalai, we manage to prove the following optimal bound on fractional Helly number for families of open sets in a surface: Let F be a finite family of open sets in a surface S such that the intersection of any subfamily of F is either empty, or path-connected. Then the fractional Helly number of F is at most three. This also settles a conjecture of Holmsen, Kim, and Lee about an existence of a (p,q)-theorem for open subsets of a surface.
Publishing Year
Date Published
2020-06-01
Proceedings Title
36th International Symposium on Computational Geometry
Volume
164
Page
61:1-61:13
Conference
SoCG: Symposium on Computational Geometry
Conference Location
Zürich, Switzerland
Conference Date
2020-06-22 – 2020-06-26
ISSN
IST-REx-ID

Cite this

Patakova Z. Bounding radon number via Betti numbers. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020:61:1-61:13. doi:10.4230/LIPIcs.SoCG.2020.61
Patakova, Z. (2020). Bounding radon number via Betti numbers. In 36th International Symposium on Computational Geometry (Vol. 164, p. 61:1-61:13). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.61
Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” In 36th International Symposium on Computational Geometry, 164:61:1-61:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.61.
Z. Patakova, “Bounding radon number via Betti numbers,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164, p. 61:1-61:13.
Patakova Z. 2020. Bounding radon number via Betti numbers. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164. 61:1-61:13.
Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” 36th International Symposium on Computational Geometry, vol. 164, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 61:1-61:13, doi:10.4230/LIPIcs.SoCG.2020.61.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
Access Level
OA Open Access
Date Uploaded
2020-06-23
MD5 Checksum
d0996ca5f6eb32ce955ce782b4f2afbe


Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1908.01677

Search this title in

Google Scholar
ISBN Search