About an Erdős-Grünbaum conjecture concerning piercing of non-bounded convex sets (Q2351027)

From MaRDI portal
scientific article
Language Label Description Also known as
English
About an Erdős-Grünbaum conjecture concerning piercing of non-bounded convex sets
scientific article

    Statements

    About an Erdős-Grünbaum conjecture concerning piercing of non-bounded convex sets (English)
    0 references
    0 references
    0 references
    0 references
    26 June 2015
    0 references
    The paper investigates versions of Helly's Theorem for infinitely many sets. The \textit{piercing number} of a family of sets is the smallest size of a set that intersects all of them. The piercing number is considered infinite, if no such finite set exists. A family of sets is said to satisfy the \((p,q)\)-property, if it has at least \(p\) sets, and for any \(p\) of its sets, there is a subfamily of \(q\) sets of those \(p\) sets, which has piercing number one. \textit{N. Alon} and \textit{D. J. Kleitman} [Adv. Math. 96, No. 1, 103--112 (1992; Zbl 0768.52001)] proved the so-called \((p,q)\) theorem: Given positive integers \(p\geq q\geq d+1\), there is a constant \(c=c(p,q,d)\) such that every finite family \(\mathcal F\) of closed convex sets in \(\mathbb{R}^d\) with the \((p,q)\)-property has piercing number at most \(c\). The main result of the paper is the following extension of the \((p,q)\)-theorem: Given positive integers \(p\geq q\geq d+1\), (i) if \(q\geq p-q+(d+1) \) and \(\mathcal F\) is a family of closed convex sets in \(\mathbb{R}^d\) containing at least \(p-q+1\) bounded members and satisfying the \((p,q)\)-property, then the piercing number of \(\mathcal F\) is at most \(\xi(q-1,d,d-1)\xi(p,q,d)+p-q+1\), where \(\xi(a,b,d)\) is the least possible value of \(c(a,b,d)\) in the \((p,q)\)-theorem, and (ii) if \(q< p-q+(d+1) \), then there is a family \(\mathcal F\) of closed convex sets in \(\mathbb{R}^d\), containing infinitely many bounded members, satisfying the \((p,q)\)-property and having infinite piercing number.
    0 references
    Helly's theorem
    0 references
    Hadwiger-Debrunner theorem
    0 references
    intersection structure
    0 references
    piercing number
    0 references

    Identifiers