Helly numbers of acyclic families
29
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
29
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
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
Voir
- d? denote
- dimension
- space sometimes refers
- topological space
- any sub-family
- arc-wise connected
Publié par
Langue
English
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 particulardRd=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 inRd[29] or forms a good cover in Rd 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 Eric.Colin.De.Verdiere@ens.fr †ail:rance.emraP,F,sisuJeueistimaedquMaut´ethtsti,enIuCirraeieetMierrt´ePersivinU,IVsiraPCMPU ginot@math.jussieu.fr ‡Project-team VEGAS, INRIA, Laboratoire Lorrain de Recherche en Informatique et Automatique, Nancy, France. email:oc@inria.fraxivreg.ao
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,dRd=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. (Recall1We 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 ˜ Hi(TGQ) = 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: givenA1 . . . Anof convex sets inRdand lettingTidenote the set of non-oriented lines intersectingAi, we can obtain bound on the Helly numberhof{T1 . . . Tn}under certain conditions on the geometry of theAi. Specifically, we obtain thathis (i) at most 2d−1(2d−1) when theAiare disjoint parallelotopes inRd, (ii) at most 10 when theAiare disjoint translates of a convex set inR2, and (iii) at most 4d− 12,2 (resp. 15, 20, 20) when theAiare disjoint equal-radius balls inRdwith 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 inRdhas the homotopy type ofRPd−1, and the familyTiis thus only acyclic with some slack; also, the bound 4d−2 when 1To 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
