LIPIcs.SoCG.2020.61.pdf
- Filesize: 0.61 MB
- 13 pages
Document
Bounding Radon Number via Betti Numbers
Author
Zuzana Patáková 
-
Part of:
Volume:
36th International Symposium on Computational Geometry (SoCG 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-08
File
Document Identifiers
Author Details
Acknowledgements
First and foremost, I am very grateful to Pavel Paták for numerous discussions, helpful suggestions and a proofreading. Many thanks to Xavier Goaoc for his feedback and comments, which have been very helpful in improving the overall presentation. I also thank Endre Makai for pointers to relevant literature, especially to the book [Soltan, 1984]. Finally, many thanks to Natan Rubin for several discussions at the very beginning of the project.
Cite As Get BibTex
Zuzana Patáková. Bounding Radon Number via Betti Numbers. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 61:1-61:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.61
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.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Geometric topology
- Theory of computation → Computational geometry
Keywords
- Radon number
- topological complexity
- constrained chain maps
- fractional Helly theorem
- convexity spaces
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
N. Alon, G. Kalai, J. Matoušek, and R. Meshulam. Transversal numbers for hypergraphs arising in geometry. Adv. Appl. Math., 29:79-101, 2002.
- D. C. Kay and E. W. Womble. Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers. Pacific Journal of Mathematics, 38, August 1971. URL: https://doi.org/10.2140/pjm.1971.38.471.
- J. De Loera, X. Goaoc, F. Meunier, and N. Mustafa. The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg. Bulletin of the American Mathematical Society, June 2017. URL: https://doi.org/10.1090/bull/1653.
- P. Erdős and M. Simonovits. Supersaturated graphs and hypergraphs. Combinatorica, 3(2):181-192, 1983. URL: https://doi.org/10.1007/BF02579292.
-
R. Fulek and J. Kynčl. The ℤ₂-genus of Kuratowski minors. In 34th International Symposium on Computational Geometry, volume 99 of LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018.
- X. Goaoc, I. Mabillard, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. On generalized Heawood inequalities for manifolds: a van Kampen-Flores-type nonembeddability result. Israel J. Math., 222(2):841-866, 2017. URL: https://doi.org/10.1007/s11856-017-1607-7.
-
X. Goaoc, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. Bounding Helly numbers via Betti numbers. In A journey through discrete mathematics, pages 407-447. Springer, Cham, 2017.
-
A. Holmsen, M. Kim, and S. Lee. Nerves, minors, and piercing numbers. Trans. Amer. Math. Soc., 371:8755–8779, 2019.
- A. Holmsen and D. Lee. Radon numbers and the fractional Helly theorem, 2019. URL: http://arxiv.org/abs/1903.01068.
- R. E. Jamison-Waldner. Partition numbers for trees and ordered sets. Pacific J. Math., 96(1):115-140, 1981. URL: https://projecteuclid.org:443/euclid.pjm/1102734951.
- G. Kalai and Z. Patáková. Intersection patterns of planar sets, 2019. URL: http://arxiv.org/abs/1907.00885.
- F. W. Levi. On Helly’s theorem and the axioms of convexity. The Journal of the Indian Mathematical Society, 15(0):65-76, 1951. URL: http://www.informaticsjournals.com/index.php/jims/article/view/17070.
- J. Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002. URL: https://doi.org/10.1007/978-1-4613-0039-7.
- P. Paták and M. Tancer. Embeddings of k-complexes into 2k-manifolds, 2019. URL: http://arxiv.org/abs/1904.02404.
- J. Radon. Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten. Mathematische Annalen, 83(1):113-115, March 1921. URL: https://doi.org/10.1007/BF01464231.
-
F. P. Ramsey. On a problem in formal logic. Proc. London Math. Soc., 30:264 - -286, 1929.
-
V. P. Soltan. Vvedenie v aksiomaticheskuyu teoriyu vypuklosti. "Shtiintsa", Kishinev, 1984. In Russian, with English and French summaries.
-
M. L. J. van de Vel. Theory of convex structures, volume 50 of North-Holland Mathematical Library. North-Holland Publishing Co., Amsterdam, 1993.
- H. Whitney. The self-intersections of a smooth n-manifold in 2n-space. Annals of Mathematics, 45(2):220-246, 1944. URL: http://www.jstor.org/stable/1969265.