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 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 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 nonnegative integer i less or equal to (d1)/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 nonembeddability results with a Ramseybased approach to build, given an arbitrary simplicial complex K, some wellbehaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest.

Keywords: 
Betti numbers; Hellytype theorem; Ramsey’s theorem, Embedding of simplicial complexes; Homological almostembedding

Conference Title:

SoCG: Symposium on Computational Geometry

Volume: 
34

Conference Dates:

June 22  25, 2015

Conference Location:

Eindhoven, Netherlands

ISBN:

9781450325943

Publisher:

ACM

Location:

Dagstuhl

Date Published:

20150101

Start Page: 
507

End Page:

521

Copyright Statement: 
CCBY

URL: 

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 SVV2014260103. ZP and MT were partially
supported by the ERC Advanced Grant No. 267165 and by the project CEITI (GACR P202/12/G061)
of the Czech Science Foundation. UW was partially supported by the Swiss National Science Foundation
(grants SNSF200020138230 and SNSFPP00P2138948). Part of this work was done when XG was affiliated with INRIA Nancy GrandEst and when MT was affiliated with Institutionen för matematik, Kungliga Tekniska Högskolan, then IST Austria.

Open access: 
yes (OA journal) 