29 Pages

English

Helly numbers of acyclic families

ERIC COLIN DE VERDIERE - pefav

Free trial

Gain access to the library to view online
Learn more

About
Information

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

From the same publisher

Machine Learning Summer School Ile de Re Learning with sparsity inducing norms slides

Supervised learning for computer vision: Theory and algorithms Introduction

Digital mathematics libraries: The good the bad the ugly

Thierry LEQUEU Juin DATA076 Fichier PROJETS IUT5 DOC

Learning on images with segmentation graph kernels

Construction of Bent Functions via Niho Power Functions

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 ﬁnite 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 ﬁnitely many convex sets inRd[29] or forms a good cover in Rd our purposes, a[30]. (Forgood coveris a ﬁnite 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

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 ﬁnite 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 deﬁnition that is a weakened version of acyclicity:

Deﬁnition 2.A ﬁnite 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(TG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 ﬁnite 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. Speciﬁcally, 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 diﬀerent: the intersection of a ﬁnite sub-family in an acyclic family can consist of severalQ-homology cells.

Internship/Work Experience Reports Prose Poetry Online Books The catalogue The whole community

Helly numbers of acyclic families

Documents

Education

Dimensión

Topological space

YouScribe

The catalogue

Service

Conditions