论文标题
彩色分数Helly定理的最佳界限
Optimal bounds for the colorful fractional Helly theorem
论文作者
论文摘要
众所周知的分数Helly定理和彩色的Helly定理可以合并为所谓的彩色分数Helly定理。它指出：对于（0，1] $中的每$α\，每个非负整数$ d $，都有$β_{col} =β_{col}（α，d）\ in（0，1] $，带有以下属性。令$ \ Mathcal {f} _1，\ dots，\ Mathcal {f} _ {d+1} $成为有限的非公百货家庭，$ \ Mathbb { n_ {d+1} $。非空交叉点（彩色$（D+1）$ - 元组是$（d+1）$ - 元组$（f_1，\ dots，f_ {d+1}）$ 2014年，Bárány，Fodor，Montejano，Oliveros和Pór首先用$β_{col} =α/（D+1）$对五颜六色的分数Helly定理进行了说明和证明。在2017年，Kim证明了具有更好功能$β_{col} $的定理，当$α$倾向于$ 1 $时，尤其是$ 1 $。 Kim还猜想了$β_{col}（α，d）$的最佳结合是什么，并为最佳结合提供了上限示例。猜想的结合与（非色）分数Helly定理的最佳边界相吻合，由Eckhoff和Kalai在1984年左右独立证明。 我们通过将Kalai的方法扩展到彩色场景来验证Kim的猜想。此外，当我们允许几组相同颜色时，我们在更通用的环境中也获得了最佳界限。
The well known fractional Helly theorem and colorful Helly theorem can be merged into the so called colorful fractional Helly theorem. It states: For every $α\in (0, 1]$ and every non-negative integer $d$, there is $β_{col} = β_{col}(α, d) \in (0, 1]$ with the following property. Let $\mathcal{F}_1, \dots, \mathcal{F}_{d+1}$ be finite nonempty families of convex sets in $\mathbb{R}^d$ of sizes $n_1, \dots, n_{d+1}$ respectively. If at least $αn_1 n_2 \cdots n_{d+1}$ of the colorful $(d+1)$-tuples have a nonempty intersection, then there is $i \in [d+1]$ such that $\mathcal{F}_i$ contains a subfamily of size at least $β_{col} n_i$ with a nonempty intersection. (A colorful $(d+1)$-tuple is a $(d+1)$-tuple $(F_1, \dots , F_{d+1})$ such that $F_i$ belongs to $\mathcal{F}_i$ for every $i$.) The colorful fractional Helly theorem was first stated and proved by Bárány, Fodor, Montejano, Oliveros, and Pór in 2014 with $β_{col} = α/(d+1)$. In 2017 Kim proved the theorem with better function $β_{col}$, which in particular tends to $1$ when $α$ tends to $1$. Kim also conjectured what is the optimal bound for $β_{col}(α, d)$ and provided the upper bound example for the optimal bound. The conjectured bound coincides with the optimal bounds for the (non-colorful) fractional Helly theorem proved independently by Eckhoff and Kalai around 1984. We verify Kim's conjecture by extending Kalai's approach to the colorful scenario. Moreover, we obtain optimal bounds also in more general setting when we allow several sets of the same color.
