Abstract
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 α ELEMENT OF (0, 1] and every non-negative integer d, there is β_{col} = β_{col}(α, d) ELEMENT OF (0, 1] with the following property.
Let ℱ1, ... , ℱ_{d+1} be finite nonempty families of convex sets in ℝ^d of sizes n1, ... , n_{d+1}, respectively. If at least α n1 n1 MIDLINE HORIZONTAL ELLIPSIS n_{d+1} of the colorful (d+1)-tuples have a nonempty intersection, then there is i ELEMENT OF [d+1] such that ℱ_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 (F1, ... , F_{d+1}) such that F_i belongs to ℱ_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 a more general setting when we allow several sets of the same color.