Bounding Helly numbers via Betti numbers Conference Paper

Author(s): Goaoc, Xavier; Paták, Pavel; Patáková, Zuzana; Tancer, Martin; Wagner, Uli
Title: Bounding Helly numbers via Betti numbers
Title Series: LIPIcs
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 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.
Keywords: Betti numbers; Helly-type theorem; Ramsey’s theorem, Embedding of simplicial complexes; Homological almost-embedding
Conference Title: SoCG: Symposium on Computational Geometry
Volume: 34
Conference Dates: June 22 - 25, 2015
Conference Location: Eindhoven, Netherlands
ISBN: 978-1-4503-2594-3
Publisher: ACM  
Location: Dagstuhl
Date Published: 2015-01-01
Start Page: 507
End Page: 521
Copyright Statement: CC-BY
DOI: 10.4230/LIPIcs.SOCG.2015.507
Notes: PP, ZP and MT were partially supported by the Charles University Grant GAUK 421511. ZP was partially supported by the Charles University Grant SVV-2014-260103. ZP and MT were partially supported by the ERC Advanced Grant No. 267165 and by the project CE-ITI (GACR P202/12/G061) of the Czech Science Foundation. UW was partially supported by the Swiss National Science Foundation (grants SNSF-200020-138230 and SNSF-PP00P2-138948). Part of this work was done when XG was affiliated with INRIA Nancy Grand-Est and when MT was affiliated with Institutionen för matematik, Kungliga Tekniska Högskolan, then IST Austria.
Open access: yes (OA journal)
IST Austria Authors
  1. Uli Wagner
    46 Wagner
  2. Martin Tancer
    8 Tancer
Related IST Austria Work