Helly numbers of acyclic families

DOI10.1016/J.AIM.2013.11.004zbMATH Open1301.52019arXiv1101.6006OpenAlexW2963422761MaRDI QIDQ2445970

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

Publication date: 15 April 2014

Published in: Advances in Mathematics (Search for Journal in Brave)

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 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.

Full work available at URL: https://arxiv.org/abs/1101.6006

zbMATH Keywords

spectral sequencesHelly numberHelly's theoremnerve theoremtopological combinatoricsgeometric transversalssimplicial posetLeray number

Mathematics Subject Classification ID

Combinatorial aspects of simplicial complexes (05E45) Helly-type theorems and geometric transversal theory (52A35) Spectral sequences in algebraic topology (55T99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometric permutations of disjoint translates of convex sets
• A Helly-type theorem for line transversals to disjoint unit balls
• Lower bounds to Helly numbers of line transversals to disjoint congruent balls
• Geometric permutations of disjoint unit spheres
• Sharp bounds on geometric permutations of pairwise disjoint balls in \(\mathbb{R}^d\)
• Line transversals to disjoint balls
• Helly-type theorems for line transversals to disjoint unit balls
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• A Vietoris Mapping Theorem for Homotopy
• Simplicial homotopy theory
• Intersections of Leray complexes and regularity of monomial ideals
• Helly-type theorems and generalized linear programming
• On the imbedding of systems of compacta in simplicial complexes
• Transversal numbers for hypergraphs arising in geometry
• Group actions and Helly's theorem
• Survey article: an elementary illustrated introduction to simplicial sets
• Approximation of definable sets by compact families, and upper bounds on homotopy and homology
• Δ-SETS I: HOMOTOPY THEORY
• Posets, regular CW complexes and Bruhat order
• f-vectors and h-vectors of simplicial posets
• The geometric realization of a semi-simplicial complex
• Leray numbers of projections and a topological Helly-type theorem
• A new topological Helly theorem and some transversal results
• Helly Type Theorems Derived From Basic Singular Homology
• Nerves, fibers and homotopy groups
• Morris's pigeonhole principle and the Helly theorem for unions of convex sets
• Proof of Grünbaum's conjecture on common transversals for translates
• No Helly theorem for stabbing translates by lines in \(\mathbb{R}^3\)
• Über ein Problem aus der kombinatorischen Geometrie
• On common transversals
• A conjecture of Grünbaum on common transversals.
• Bounding the piercing number
• On Components in Some Families of Sets
• A short proof of an interesting Helly-type theorem
• A Helly-type theorem for unions of convex sets
• Geometric permutations of balls with bounded size disparity.
• Foundations of a theory of convexity on affine Grassmann manifolds
• On the homology structure of submersions
• Cremona convexity, frame convexity and a theorem of Santaló

Cited In (12)

• Multinerves and Helly numbers of acyclic families
• Colorful theorems for strong convexity
• Leray numbers of complexes of graphs with bounded matching number
• Quantitative combinatorial geometry for concave functions
• Some new results on geometric transversals
• Bounding Helly Numbers via Betti Numbers
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• The intersection of a matroid and an oriented matroid
• Helly’s theorem: New variations and applications
• Interleaving Mayer-Vietoris spectral sequences
• A counterexample to Wegner's conjecture on good covers
• Nerves, minors, and piercing numbers

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Multinerves and Helly numbers of acyclic families 👍 👎
• On acyclic and cyclic hypergraphs 👍 👎
• Counting acyclic hypergraphs 👍 👎
• Enumeration of maximum acyclic hypergraphs 👍 👎
• On Helly families of maximal size 👍 👎
• Helly-type hypergraphs and Sperner families 👍 👎
• Enumeration Degrees and Enumerability of Familes 👍 👎
• THE HULL NUMBER OF POWERS OF CYCLES 👍 👎

This page was built for publication: Helly numbers of acyclic families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2445970)