Bounding radon number via Betti numbers
LIPIcs
Patakova, Zuzana
ddc:510
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.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2020
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://research-explorer.app.ist.ac.at/record/7989
https://research-explorer.app.ist.ac.at/download/7989/8005
Patakova Z. Bounding radon number via Betti numbers. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.61">10.4230/LIPIcs.SoCG.2020.61</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.SoCG.2020.61
info:eu-repo/semantics/altIdentifier/issn/18688969
info:eu-repo/semantics/altIdentifier/isbn/9783959771436
info:eu-repo/semantics/altIdentifier/arxiv/1908.01677
https://creativecommons.org/licenses/by/4.0/
info:eu-repo/semantics/openAccess