Transversal numbers for hypergraphs arising in geometry
type: Item
instance of: scholarly article
title: Transversal numbers for hypergraphs arising in geometry
zbMATH Open document ID: 1027.52003
DOI: 10.1016/S0196-8858(02)00003-9
author: Noga Alon
author: Gil Kalai
author: Jiří Matoušek
author: Roy Meshulam
published in: Advances in Applied Mathematics
publication date: 2003-03-26T00:00:00Z
review text: In 1992 \textit{N. Alon} and \textit{D. J. Kleitman} [Adv. Math. 96, 103-112 (1992; Zbl 0768.52001)] proved a conjecture formulated in 1957 by \textit{H. Hadwiger} and \textit{H. Debrunner} [Arch. Math. 8, 309-313 (1957; Zbl 0080.15404)] extending Helly's theorem, viz. that if \({\mathcal F}\) is a family of convex sets in \({\mathbb{R}^{d}}\) satisfying the \((p,q)\) condition for some \(p\geq q\geq d+1\), then the transversal number of \(\mathcal{F}\) is bounded by a function of \(d\), \(p\) and \(q\), where (i) a system of sets is said to satisfy the \((p,q)\) condition if out of any \(p\) elements of the system, some \(q\) sets have a point in common and (ii) the transversal number of \({\mathcal F}\) is the minimum cardinality of the subset that intersects all \(F \in {\mathcal F}\). In this paper the authors, using similar methods, prove a \((p,q)\) theorem for abstract set systems \({\mathcal F}\). The main result indicates that in an absract setting the appropriate fractional Helly property is sufficient to derive the existence of weak \(\varepsilon\)-nets and validity of a \((p,q)\) theorem. As a consequence a topological \((p,d+1)\) theorem is derived (where \({\mathcal F}\) is a good cover in \(\mathbb {R}^{d}\) or more generally that the nerve of \({\mathcal F}\) is \(d\)-Leray) as well a \((p,2^{d})\) theorem for convex lattice sets in \(\mathbb{Z}^{d}\). Also some examples are given to show that some of the assumptions cannot be weakened.
Mathematics Subject Classification ID: 52A35
Mathematics Subject Classification ID: 05D15
zbMATH DE Number: 1888302
zbMATH Keywords: hypergraph
zbMATH Keywords: transversal numbers
zbMATH Keywords: \((p,q)\) theorem
zbMATH Keywords: Helly's theorem
reviewed by: Semin Akdoǧan
MaRDI profile type: Publication
Wikidata QID: Q105333976
cites work: Point Selections and Weak ε-Nets for Convex Hulls
cites work: Bounding the piercing number
cites work: Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
cites work: Almost regular sequences and Betti numbers
cites work: A generalization of Caratheodory's theorem
cites work: Improved bounds on weak \(\varepsilon\)-nets for convex sets
cites work: Bounding the vertex cover number of a hypergraph
cites work: Convexity in cristallographical lattices
cites work: An upper-bound theorem for families of convex sets
cites work: Q3770569
cites work: Über eine Variante zum Hellyschen Satz
cites work: On a Gallai-type problem for lattices
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Partition numbers for trees and ordered sets
cites work: Intersection patterns of convex sets
cites work: Q4550929
cites work: A Problem of Geometry in R n
cites work: Almost tight bounds for \(\epsilon\)-nets
cites work: Kneser's conjecture, chromatic number, and homotopy
cites work: On the Geometry and Computational Complexity of Radon Partitions in the Iinteger Lattice
cites work: Q3351113
cites work: Q4125422
cites work: The Upper Bound Conjecture and Cohen-Macaulay Rings
cites work: d-collapsing and nerves of families of convex sets
cites work: Q4400994
Recommended article: Bounded VC-dimension implies a fractional Helly theorem
Recommended article: Discrete and lexicographic Helly-type theorems
Recommended article: Helly's Theorem with Volumes
Recommended article: Q3822773
Recommended article: Helly’s theorem: New variations and applications
Recommended article: Q4274009
Recommended article: Helly and Klee type intersection theorems for finitary connected paved spaces
Recommended article: Q4854183
Recommended article: Separoids, their categories and a Hadwiger-type theorem for transversals
Recommended article: Bounding the piercing number
description: scientific article; zbMATH DE number 1888302