Transversal numbers for hypergraphs arising in geometry (Q1865252)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Transversal numbers for hypergraphs arising in geometry |
scientific article |
Statements
Transversal numbers for hypergraphs arising in geometry (English)
0 references
26 March 2003
0 references
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.
0 references
hypergraph
0 references
transversal numbers
0 references
\((p,q)\) theorem
0 references
Helly's theorem
0 references
0 references