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
fractional colorful Helly theorem
0 references
convex set
0 references