Document Open Access Logo

Bounding Helly Numbers via Betti Numbers

Authors Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.507.pdf
  • Filesize: 0.6 MB
  • 15 pages

Document Identifiers

Author Details

Xavier Goaoc
Pavel Paták
Zuzana Patáková
Martin Tancer
Uli Wagner

Cite As Get BibTex

Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. Bounding Helly Numbers via Betti Numbers. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 507-521, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.507

Abstract

We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^d such that the ith reduced Betti number (with Z_2 coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every non-negative integer i less or equal to (d-1)/2, then F has Helly number at most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number.

Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest.

Subject Classification

Keywords
  • Helly-type theorem
  • Ramsey’s theorem
  • Embedding of simplicial complexes
  • Homological almost-embedding
  • Betti numbers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Amenta. Helly-type theorems and generalized linear programming. Discrete & Computational Geometry, 12:241-261, 1994. Google Scholar
  2. N. Amenta. A short proof of an interesting Helly-type theorem. Discrete & Computational Geometry, 15:423-427, 1996. Google Scholar
  3. E. G. Bajmóczy and I. Bárány. On a common generalization of Borsuk’s and Radon’s theorem. Acta Math. Acad. Sci. Hungar., 34(3-4):347-350, 1979. Google Scholar
  4. M. Bestvina, M. Kapovich, and B. Kleiner. Van Kampen’s embedding obstruction for discrete groups. Invent. Math., 150(2):219-235, 2002. Google Scholar
  5. A. Björner. Nerves, fibers and homotopy groups. Journal of Combinatorial Theory, Series A, 102(1):88-93, 2003. Google Scholar
  6. K. Borsuk. On the imbedding of systems of compacta in simplicial complexes. Fundamenta Mathematicae, 35:217-234, 1948. Google Scholar
  7. É. Colin de Verdière, G. Ginot, and X. Goaoc. Multinerves and Helly numbers of acyclic families. In Proceedings of the 2012 symposium on Computational Geometry, SoCG'12, pages 209-218, 2012. URL: http://arxiv.org/abs/1101.6006.
  8. H. Debrunner. Helly type theorems derived from basic singular homology. American Mathematical Monthly, 77:375-380, 1970. Google Scholar
  9. J. Eckhoff. Helly, Radon and Carathéodory type theorems. In P.M. Gruber and J.M. Wills, editors, Handbook of Convex Geometry, pages 389-448. North Holland, 1993. Google Scholar
  10. A. I. Flores. Über die Existenz n-dimensionaler Komplexe, die nicht in den ℝ^2n topologisch einbettbar sind. Ergeb. Math. Kolloqu., 5:17-24, 1933. Google Scholar
  11. X. Goaoc, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. Bounding Helly numbers via Betti numbers. URL: http://arxiv.org/abs/1310.4613.
  12. A. Hatcher. Algebraic Topology. Cambridge University Press, Cambridge, UK, 2002. Google Scholar
  13. E. Helly. Über Mengen konvexer Körper mit gemeinschaftlichen Punkten. Jahresbericht Deutsch. Math. Verein., 32:175-176, 1923. Google Scholar
  14. E. Helly. Über Systeme von abgeschlossenen Mengen mit gemeinschaftlichen Punkten. Monaths. Math. und Physik, 37:281-302, 1930. Google Scholar
  15. G. Kalai. Combinatorial expectations from commutative algebra. In I. Peeva and V. Welker, editors, Combinatorial Commutative Algebra, volume 1(3), pages 1729-1734. Oberwolfach Reports, 2004. Google Scholar
  16. G. Kalai and R. Meshulam. Leray numbers of projections and a topological Helly-type theorem. Journal of Topology, 1:551-556, 2008. Google Scholar
  17. H. Maehara. Helly-type theorems for spheres. Discrete & Computational Geometry, 4(1):279-285, 1989. Google Scholar
  18. J. Matoušek. Using the Borsuk-Ulam Theorem. Springer-Verlag, Berlin, 2003. Google Scholar
  19. J. Matoušek. A Helly-type theorem for unions of convex sets. Discrete & Computational Geometry, 18:1-12, 1997. Google Scholar
  20. S. A. Melikhov. The van Kampen obstruction and its relatives. Proc. Steklov Inst. Math., 266(1):142-176, 2009. Google Scholar
  21. L. Montejano. A new topological Helly theorem and some transversal results. Discrete & Computational Geometry, 52(2):390-398, 2014. Google Scholar
  22. J. R. Munkres. Elements of Algebraic Topology. Addison-Wesley, Menlo Park, CA, 1984. Google Scholar
  23. F. P. Ramsey. On a problem in formal logic. Proc. London Math. Soc., 30:264–-286, 1929. Google Scholar
  24. A. Shapiro. Obstructions to the imbedding of a complex in a euclidean space. I. The first obstruction. Ann. of Math. (2), 66:256-269, 1957. Google Scholar
  25. M. Sharir and E. Welzl. A combinatorial bound for linear programming and related problems. In Proc. 9th Sympos. on Theo. Aspects of Comp. Science, pages 569-579, 1992. Google Scholar
  26. R. I. Soare. Computability theory and differential geometry. Bull. Symbolic Logic, 10(4):457-486, 2004. Google Scholar
  27. M. Tancer. Intersection patterns of convex sets via simplicial complexes: A survey. In J. Pach, editor, Thirty Essays on Geometric Graph Theory, pages 521-540. Springer New York, 2013. Google Scholar
  28. E. R. van Kampen. Komplexe in euklidischen Räumen. Abh. Math. Sem. Univ. Hamburg, 9:72-78, 1932. Google Scholar
  29. U. Wagner. Minors in random and expanding hypergraphs. In Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG), pages 351 - 360, 2011. Google Scholar
  30. R. Wenger. Helly-type theorems and geometric transversals. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete & Computational Geometry, chapter 4, pages 73-96. CRC Press LLC, Boca Raton, FL, 2nd edition, 2004. Google Scholar
  31. W.-T. Wu. On the realization of complexes in euclidean spaces. I, II, III. Acta Math. Sinica (English transl. of I and III in Sci. Sinica), 5:505-552, 1955. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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