Optimal bounds for the colorful fractional Helly theorem

The well known fractional Helly theorem and colorful Helly theorem can be merged into so called colorful fractional Helly theorem. It states: For every alpha in (0, 1] and every non-negative integer d, there is beta = beta(alpha, d) in (0, 1] with the following property. Let F_1, ..., F_{d+1} be finite nonempty families of convex sets in R^d of sizes n_1, ..., n_{d+1} respectively. If at least alpha n_1 n_2 ... n_{d+1} of the colorful (d+1)-tuples have a nonempty intersection, then there is i in [d+1] such that F_i contains a subfamily of size at least b n_i. (A colorful (d+1)-tuple is a (d+1)-tuple (C_1,...,C_{d+1}) such that C_i belongs to 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 beta = alpha/(d+1). In 2017 Kim proved the theorem with better function beta, which in particular tends to 1 when alpha tends to 1. Kim also conjectured what is the optimal bound for beta(alpha, 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 prove Kim's conjecture by extending Kalai's approach to the colorful scenario. Moreover, we obtain bounds for other collections of sets, not just colorful (d+1)-tuples.

This is a joint work with Afshin Goodarzi and Martin Tancer.