Bounding radon number via Betti numbers
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.
Download
Conference Paper
| Published
| English
Scopus indexed
Author
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
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume
164
Article Number
61:1-61:13
Conference
SoCG: Symposium on Computational Geometry
Conference Location
Zürich, Switzerland
Conference Date
2020-06-22 – 2020-06-26
ISBN
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. 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). 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, Vol. 164. 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.
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, 61:1-61:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, 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)
File Name
2020_LIPIcsSoCG_Patakova_61.pdf
645.42 KB
Access Level
Open Access
Date Uploaded
2020-06-23
MD5 Checksum
d0996ca5f6eb32ce955ce782b4f2afbe
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1908.01677