Search Results

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 α ∈ (0, 1] and every non-negative integer d, there is β_{col} = β_{col}(α, d) ∈ (0, 1] with the following property. Let ℱ₁, … , ℱ_{d+1} be finite nonempty families of convex sets in ℝ^d of sizes n₁, … , n_{d+1}, respectively. If at least α n₁ n₂ ⋯ n_{d+1} of the colorful (d+1)-tuples have a nonempty intersection, then there is i ∈ [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 (F₁, … , 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.