Bounding the piercing number (Q1892406): Difference between revisions

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.