Document Open Access Logo

Bounding Radon Number via Betti Numbers

Author Zuzana Patáková

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2020.61.pdf
  • Filesize: 0.61 MB
  • 13 pages

Document Identifiers

Related Versions

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)
    0
    PDF Downloads
    0
    Metadata Views

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.

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

Author Details

Zuzana Patáková
  • Computer Science Institute, Charles University, Prague, Czech Republic
  • IST Austria, Klosterneuburg, Austria

Funding

The research stay of the author at IST Austria is funded by the project Improvement of internationalization in the field of research and development at Charles University, through the support of quality projects MSCA-IF (CZ.02.2.69/0.0/0.0/17_050/0008466).

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.

References

  1. N. Alon, G. Kalai, J. Matoušek, and R. Meshulam. Transversal numbers for hypergraphs arising in geometry. Adv. Appl. Math., 29:79-101, 2002. Google Scholar
  2. 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.
  3. 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.
  4. P. Erdős and M. Simonovits. Supersaturated graphs and hypergraphs. Combinatorica, 3(2):181-192, 1983. URL: https://doi.org/10.1007/BF02579292.
  5. 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. Google Scholar
  6. 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.
  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. Google Scholar
  8. A. Holmsen, M. Kim, and S. Lee. Nerves, minors, and piercing numbers. Trans. Amer. Math. Soc., 371:8755–8779, 2019. Google Scholar
  9. A. Holmsen and D. Lee. Radon numbers and the fractional Helly theorem, 2019. URL: http://arxiv.org/abs/1903.01068.
  10. 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.
  11. G. Kalai and Z. Patáková. Intersection patterns of planar sets, 2019. URL: http://arxiv.org/abs/1907.00885.
  12. 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.
  13. 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.
  14. P. Paták and M. Tancer. Embeddings of k-complexes into 2k-manifolds, 2019. URL: http://arxiv.org/abs/1904.02404.
  15. 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.
  16. F. P. Ramsey. On a problem in formal logic. Proc. London Math. Soc., 30:264 - -286, 1929. Google Scholar
  17. V. P. Soltan. Vvedenie v aksiomaticheskuyu teoriyu vypuklosti. "Shtiintsa", Kishinev, 1984. In Russian, with English and French summaries. Google Scholar
  18. M. L. J. van de Vel. Theory of convex structures, volume 50 of North-Holland Mathematical Library. North-Holland Publishing Co., Amsterdam, 1993. Google Scholar
  19. 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.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact