Bounding helly numbers via betti numbers Book Section

Author(s): Goaoc, Xavier; Paták, Pavel; Patáková, Zuzana; Tancer, Martin; Wagner, Uli
Article/Chapter Title: Bounding helly numbers via betti numbers
Affiliation IST Austria
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 Rd such that βi(∩G)≤b for any G⊊F and every 0 ≤ i ≤ [d/2]-1 then F has Helly number at most h(b, d). Here βi denotes the reduced Z2-Betti numbers (with singular homology). These topological conditions are sharp: not controlling any of these [d/2] 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 C*(K)→C*(Rd).
Book Title: A Journey through Discrete Mathematics: A Tribute to Jiri Matousek
ISBN: 978-331944479-6
Publisher: Springer  
Date Published: 2017-10-06
Start Page: 407
End Page: 447
DOI: 10.1007/978-3-319-44479-6_17
Notes: We would like to express our immense gratitude to Jirí Matoušek, not only for raising the problem addressed in the present paper and valuable discussions about it, but, much more generally, for the privilege of having known him, as our teacher, mentor, collaborator, and friend. Through his tremendous depth and insight, and the generosity with which he shared them, he greatly influenced all of us. We further thank Jürgen Eckhoff for helpful comments on a preliminary version of the paper, and Andreas Holmsen and Gil Kalai for providing us with useful references
Open access: yes (repository)
IST Austria Authors
  1. Uli Wagner
    50 Wagner
Related IST Austria Work