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
    0 references
    0 references
    0 references
    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

    Identifiers