Bounding Helly numbers via Betti numbers

2013/10/17 by Goaoc, Xavier, Paták, Pavel, Patáková, Zuzana +2
#05D10 #55S91 #57Q35 #Algebraic Topology (math.AT) #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Primary 52A35 #secondary 05E45

paper · doi:10.48550/arxiv.1310.4613

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 \mathcal F is a finite family of subsets of \mathbb R^d such that β_i(\bigcap\mathcal G) ≤ b for any \mathcal G \subsetneq \mathcal F and every 0 ≤ i ≤ \lceil d/2 \rceil-1 then \mathcal F has Helly number at most h(b,d). Here β_i denotes the reduced \mathbb Z₂-Betti numbers (with singular homology). These topological conditions are sharp: not controlling any of these \lceil d/2 \rceil 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_*(\mathbb R^d).

Related

• Helly numbers of acyclic families
• A fractional Helly theorem for set systems with slowly growing homological shatter function
• Intersection patterns in spaces with a forbidden homological minor
• On a topological fractional Helly theorem
• Helly-type Problems