2026-07-23T05:51:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5129 2024-03-06T10:35:54Z ddc:004 open_access

Bounding Helly Numbers via Betti Numbers Goaoc, Xavier Paták, Pavel Patáková, Zuzana Tancer, Martin Wagner, Uli Helly-type theorem Ramsey’s theorem Embedding of simplicial complexes Homological almost-embedding Betti numbers 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xavier Goaoc and Pavel Paták and Zuzana Patáková and Martin Tancer and Uli Wagner 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.507 urn:nbn:de:0030-drops-51297 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.507 eng https://creativecommons.org/licenses/by/3.0/legalcode