hal-00646166, version 1

Helly numbers of acyclic families

Éric Colin de Verdière ¹, Grégory Ginot ², Xavier Goaoc ³

(24/02/2011)

• 1 :  Laboratoire d'informatique de l'école normale supérieure (LIENS)
• http://www.di.ens.fr
  CNRS : UMR8548 – Ecole normale supérieure de Paris - ENS Paris 45 Rue d'Ulm 75230 PARIS CEDEX 05 France
• 2 :  Université Pierre et Marie Curie - Paris 6 (UPMC)
• http://www.upmc.fr/
  Université Pierre et Marie Curie [UPMC] - Paris VI 4 place Jussieu - 75005 Paris France
• 3 :  VEGAS (INRIA Lorraine - LORIA)
• 
  INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL) France

Références bibliographiques

• Type de publication : Documents sans référence de publication (Preprint)
• Domaine :

  Informatique/Géométrie algorithmique

  Informatique/Mathématique discrète

  Mathématiques/Combinatoire

  Mathématiques/Topologie algébrique

  Mathématiques/Géométrie métrique

• Titre : Helly numbers of acyclic families
• Résumé : 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 Gamma. Assume that for every sub-family G of 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_Gamma+1), where d_Gamma is the smallest integer j such that every open set of Gamma has trivial Q-homology in dimension j and higher. (In particular d_{R^d} = 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.
• Langue du document : Anglais
• Date de rédaction : 24/02/2011
• Commentaire : Minor changes

• hal-00646166, version 1
• http://hal.inria.fr/hal-00646166
• oai:hal.inria.fr:hal-00646166
• Contributeur : Xavier Goaoc <>
• Soumis le : Mardi 29 Novembre 2011, 13:11:43
• Dernière modification le : Lundi 24 Septembre 2012, 14:35:44