A note on the colorful fractional Helly theorem (Q329541)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A note on the colorful fractional Helly theorem
scientific article

    Statements

    A note on the colorful fractional Helly theorem (English)
    0 references
    21 October 2016
    0 references
    A fractional colorful Helly theorem of \textit{I. Bárány} et al. [Discrete Comput. Geom. 51, No. 3, 628--642 (2014; Zbl 1298.52010)] states the following: Let \(\alpha \in (0, 1]\) and let \(\mathcal{F}_1, \dots, \mathcal{F}_{d+1}\) be finite nonempty families of convex sets in \(\mathbb R^d\) (representing \(d+1\) color classes; a \((d+1)\)-tuple \((F_1, \dots, F_{d+1})\) where \(F_i \in \mathcal F_i\) is called a \textit{colorful} \((d+1)\)-tuple). If at least \(\alpha \cdot |\mathcal F_1|\cdots |\mathcal F_{d+1}|\) of the colorful \((d+1)\)-tuples have a nonempty intersection, then there is \(i \in [d+1]\) and at least \(\beta |\mathcal F_i|\) sets in \(\mathcal F_i\) which have a nonempty intersection where \(\beta = \frac \alpha {d+1}\). The main aim of the paper is to improve this theorem when \(\alpha\) is close to \(1\). More concretely, the author achieves the same result with \(\beta = \max\left\{\frac{\alpha}{d+1}, 1 - (d+1)(1-\alpha)^{1/(d+1)}\right\}\), which tends to 1 for \(\alpha\) tending to 1. The proof is purely combinatorial using the colorful Helly theorem as a blackbox (we can take \(\beta = 1\) if \(\alpha = 1\)). Finally, the result is supplemented with an example showing an upper bound \(1 - (1-\alpha)^{1/(d+1)}\) on \(\beta\).
    0 references
    0 references
    fractional colorful Helly theorem
    0 references
    convex set
    0 references
    0 references

    Identifiers