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).
Type de document :
Chapitre d'ouvrage
Martin Loebl, Jaroslav Nešetřil, Robin Thomas. A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek , Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, pp.407-447, 2017, 〈10.1007/978-3-319-44479-6_17〉. 〈https://link.springer.com/chapter/10.1007/978-3-319-44479-6_17〉
Liste complète des métadonnées

https://hal-upec-upem.archives-ouvertes.fr/hal-01744167
Contributeur : Xavier Goaoc <>
Soumis le : mardi 27 mars 2018 - 10:55:05
Dernière modification le : mercredi 6 février 2019 - 10:22:02

Lien texte intégral

Identifiants

Citation

Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner. Bounding Helly Numbers via Betti Numbers. Martin Loebl, Jaroslav Nešetřil, Robin Thomas. A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek , Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, pp.407-447, 2017, 〈10.1007/978-3-319-44479-6_17〉. 〈https://link.springer.com/chapter/10.1007/978-3-319-44479-6_17〉. 〈hal-01744167〉

Partager

Métriques

Consultations de la notice

31