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 Hellytype theorem. More precisely, we show that for any nonnegative 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 Z2Betti 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 nonembeddability results with a Ramseybased approach to build, given an arbitrary simplicial complex K, some wellbehaved chain map C*(K)→C*(Rd).

Book Title:

A Journey through Discrete Mathematics: A Tribute to Jiri Matousek

ISBN:

9783319444796

Publisher:

Springer

Date Published:

20171006

Start Page: 
407

End Page:

447

URL: 

DOI: 
10.1007/9783319444796_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) 