Bounding Helly Numbers via Betti Numbers

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.
Type de document :
Communication dans un congrès
Lars Arge and János Pach. International Symposium on Computational Geometry, 2015, Eindhoven, Netherlands. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 34, pp.507--521, 2015, 31st International Symposium on Computational Geometry (SoCG 2015). 〈http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=5129〉. 〈10.4230/LIPIcs.SOCG.2015.507〉
Liste complète des métadonnées

https://hal-upec-upem.archives-ouvertes.fr/hal-01577897
Contributeur : Xavier Goaoc <>
Soumis le : lundi 28 août 2017 - 12:58:19
Dernière modification le : jeudi 5 juillet 2018 - 14:46:07

Lien texte intégral

Identifiants

Citation

Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner. Bounding Helly Numbers via Betti Numbers. Lars Arge and János Pach. International Symposium on Computational Geometry, 2015, Eindhoven, Netherlands. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 34, pp.507--521, 2015, 31st International Symposium on Computational Geometry (SoCG 2015). 〈http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=5129〉. 〈10.4230/LIPIcs.SOCG.2015.507〉. 〈hal-01577897〉

Partager

Métriques

Consultations de la notice

140