Helly numbers of acyclic families

Description

Helly numbers of acyclic families Eric Colin de Verdiere? Gregory Ginot† Xavier Goaoc‡ February 25, 2011 Abstract The Helly number of a family of sets with empty intersection is the size of its largest inclusion- wise minimal sub-family with empty intersection. Let F be a finite family of open subsets of an arbitrary locally arc-wise connected topological space ?. Assume that for every sub-family G ? F the intersection of the elements of G has at most r connected components, each of which is a Q-homology cell. We show that the Helly number of F is at most r(d? + 1), where d? is the smallest integer j such that every open set of ? has trivial Q-homology in dimension j and higher. (In particular dRd = d). This bound is best possible. We prove, in fact, a stronger theorem where small sub-families may have more than r connected components, each possibly with nontrivial homology in low dimension. As an application, we obtain several explicit bounds on Helly numbers in geometric transversal theory for which only ad hoc geometric proofs were previously known; in certain cases, the bound we obtain is better than what was previously known. 1 Introduction The Helly number of a family of sets with empty intersection is the size of its largest sub-family F such that (i) the intersection of all elements of F is empty, and (ii) for any proper sub-family G ( F , the intersection of the elements of G is non-empty

• d? denote


• dimension


• space sometimes refers


• topological space


• any sub-family


• arc-wise connected

Subjects

• Documents
• Education
• Dimensión
• Topological space

Informations

• Published by: pefav
• Reads: 13
• Language: English

Exrait

Helly numbers of acyclic families

´ EricColindeVerdi`ere ∗

Gre´goryGinot †

February 25, 2011

Abstract

Xavier Goaoc ‡

TheHelly numberof sets with empty intersection is the size of its largest inclusion-of a family wise minimal sub-family with empty intersection. LetFbe a finite family of open subsets of an arbitrary locally arc-wise connected topological space Γ. Assume that for every sub-family G ⊆ Fthe intersection of the elements ofGhas at mostrconnected components, each of which is aQ We-homology cell. show that the Helly number ofFis at mostr(d Γ + 1), whered Γ is the smallest integerjsuch that every open set of Γ has trivialQ-homology in dimensionjand higher. (In particulard R d =d bound is best possible.). This prove, in fact, a stronger We theorem where small sub-families may have more thanrconnected components, each possibly with nontrivial homology in low dimension. As an application, we obtain several explicit bounds on Helly numbers in geometric transversal theory for which only ad hoc geometric proofs were previously known; in certain cases, the bound we obtain is better than what was previously known.

1 Introduction

TheHelly numberof a family of sets with empty intersection is the size of its largest sub-family Fsuch that (i) the intersection of all elements ofFis empty, and (ii) for any proper sub-family G(F, the intersection of the elements ofG number is named after Eduard Thisis non-empty. Helly, whose theorems state that any inclusion-wise minimal family with empty intersection has size at mostd+ 1 if it consists of finitely many convex sets inR d [29] or forms a good cover in R d  our purposes, a[30]. (Forgood coveris a finite family of open sets where the intersection of any sub-family is empty or contractible.) In this paper, we proveHelly-type theoremsfor families of non-connected sets, that is we give upper bounds on Helly numbers for such families. (When considering the Helly number of a family of sets, we always implicitly assume that the family has empty intersection.) ´ ∗ siraarF,.ecniamel:,cEloneroamelusp´erieure,CNRS,PLiotarobafoind’reueiqatrm [e-mail] † ail:rance.emraP,F,sisuJeueistimaedquMaut´ethtsti,enIuCirraeieetMierrt´ePersivinU,IVsiraPCMPU [e-mail] ‡ Project-team VEGAS, INRIA, Laboratoire Lorrain de Recherche en Informatique et Automatique, Nancy, France. email:[e-mail]

1

1.1

Our results

Let Γ be a locally arc-wise connected topological space. We letd Γ denote the smallest integer such that every open subset of Γ has trivialQ-homology in dimensiond Γ and higher; in particular, when Γ is ad-dimensional manifold, we haved Γ =dif Γ is non-compact or non-orientable andd Γ =d+ 1 otherwise (see Lemma 23); for example,d R d =d call a family. WeFof open subsets of Γacyclicif for any non-empty sub-familyG ⊆ Fconnected component of the intersection of the elements, each ofGis aQ that, in particular, any contractible set is a homology cell.)-homology cell. (Recall 1 We prove the following Helly-type theorem:

Theorem 1.LetFbe a finite acyclic family of open subsets of a locally arc-wise connected topo- logical spaceΓ any sub-family of. IfFintersects in at mostrconnected components, then the Helly number ofFis at mostr(d Γ + 1). We show, in fact, that the conclusion of Theorem 1 holds even if the intersection of small sub- families has more thanrconnected components and has non-vanishing homology in low dimension. To state the result precisely, we need the following definition that is a weakened version of acyclicity:

Definition 2.A finite familyFof subsets of a locally arc-wise connected topological space is acyclic with slacksif for every non-empty sub-familyG ⊆ Fand everyi≥max(1 s− |G|) we have ˜ H i ( T G Q) = 0. Note that, in particular, ifs≤1,acyclic with slacksis the same asacyclic a view to-. With ward applications in geometric transversal theory, we actually prove the following strengthening of Theorem 1:

Theorem 3.LetFbe a finite family of open subsets of a locally arc-wise connected topological space Γ (i). IfFis acyclic with slacksand (ii) any sub-family ofFof cardinality at leasttintersects in at mostrconnected components, then the Helly number ofFis at mostr(max(d Γ  s t) + 1). In both Theorems 1 and 3 the openness condition can be replaced by a compactness condition (Corollary 22) under an additional mild assumption. As an application of Theorem 3 we obtain bounds on severaltransversal Helly numbers a family: givenA 1  . . .  A n of convex sets inR d and lettingT i denote the set of non-oriented lines intersectingA i , we can obtain bound on the Helly numberhof{T 1  . . .  T n }under certain conditions on the geometry of theA i . Specifically, we obtain thathis (i) at most 2 d−1 (2d−1) when theA i are disjoint parallelotopes inR d , (ii) at most 10 when theA i are disjoint translates of a convex set inR 2 , and (iii) at most 4d− 12,2 (resp. 15, 20, 20) when theA i are disjoint equal-radius balls inR d with d≥6 (resp.d= 2, 3, 4, 5).

Although similar bounds were previously known, we note that each was obtained through an ad hoc, geometric argument. The set of lines intersecting a convex set inR d has the homotopy type ofRP d−1 , and the familyT i is thus only acyclic with some slack; also, the bound 4d−2 when 1 To avoid confusion, we note that anacyclic spacesometimes refers to a homology cell in the literature (seee.g., Farb [18]). Here, the meaning is different: the intersection of a finite sub-family in an acyclic family can consist of severalQ-homology cells.

2