Bounding the piercing number
type: Item
instance of: scholarly article
title: Bounding the piercing number
zbMATH Open document ID: 0826.52006
DOI: 10.1007/BF02574042
author: Noga Alon
author: Gil Kalai
published in: Discrete \& Computational Geometry
publication date: 1995-07-05T00:00:00Z
full work available at URL: https://eudml.org/doc/131360
review text: The piercing number of a family \(H\) of sets, with respect to another family \(\mathcal F\), is the minimum number of members of \(\mathcal F\) that, between them, meet all members of \(\mathcal H\). \(\mathcal H\) is said to satisfy the \((p,q)\) property with respect to \(\mathcal F\) if for any \(p\) members of \(\mathcal H\) there is an \(F \in {\mathcal F}\) that meets all of them. Many ``Helly-type'' theorems can be stated in the form: (H) ``For every \({\mathcal H} \subset \overline {\mathcal H}\) that satisfies the \((p,q)\) property with respect to \(\mathcal F\), the piercing number of \(\mathcal H\) with respect to \(\mathcal F\) does not exceed \(c\).'' For appropriate constants \(p\), \(q\), \(c\), and families of sets \(\overline {\mathcal H}\) and \(\mathcal F\). (In particular, Helly's theorem is the case in which \(\overline {\mathcal H}\) is the family of compact convex sets in \(R^d\), \(\mathcal F\) is the family of singletons, \(p = q = d + 1\), and \(c = 1\).) The first author and D. Kleitman recently proved a conjecture of Hadwiger and Debrunner to the effect that for these \(\overline {\mathcal H}\) and \(\mathcal F\), and for all \(p \geq q \geq d + 1\), there is a finite \(c(p,q,d)\) making (H) true. This paper extends the Alon-Kleitman piercing theorem to the case when \(\mathcal F\) is as above, but \(\overline {\mathcal H}\) is the family of all unions of at most \(k\) compact convex sets in \(R^d\). It also extends it to the case when \(\overline {\mathcal H}\) consists of compact convex sets in \(R^d\), and \(\mathcal F\) consists of hyperplanes (generalizing Eckhoff's theorem); and gives various other results.
Mathematics Subject Classification ID: 52A35
zbMATH DE Number: 764224
zbMATH Keywords: Helly-type theorems
zbMATH Keywords: \((p,q)\) conjecture
zbMATH Keywords: piercing number
zbMATH Keywords: convex sets
zbMATH Keywords: Eckhoff's theorem
Wikidata QID: Q100329014
reviewed by: Robert Dawson
MaRDI profile type: Publication
cites work: Point Selections and Weak ε-Nets for Convex Hulls
cites work: A simple proof of the upper bound theorem
cites work: Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
cites work: A generalization of Caratheodory's theorem
cites work: Common tangents and common transversals
cites work: A deterministic view of random sampling and its use in geometry
cites work: Q5341481
cites work: A coloring problem
cites work: An upper-bound theorem for families of convex sets
cites work: Q4274009
cites work: A Gallai-type transversal problem in the plane
cites work: Intersectional properties of certain families of compact convex sets
cites work: Q3274656
cites work: On Components in Some Families of Sets
cites work: Über eine Variante zum Hellyschen Satz
cites work: Intersection patterns of convex sets
cites work: A Problem of Geometry in R n
cites work: Q3818127
cites work: A Generalization of Radon's Theorem
cites work: Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner
cites work: d-collapsing and nerves of families of convex sets
cites work: Q3692387
OpenAlex ID: W1983132041
DBLP publication ID: journals/dcg/AlonK95
description: scientific article; zbMATH DE number 764224