# Optimal bounds for the colorful fractional Helly theorem

Research paper by **Denys Bulavka, Afshin Goodarzi, Martin Tancer**

Indexed on: **31 Oct '20**Published on: **29 Oct '20**Published in: **arXiv - Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

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_{col}
= \beta_{col}(\alpha, 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
$\alpha 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 $\beta_{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\'ar\'any, Fodor, Montejano, Oliveros, and P\'or in 2014 with $\beta_{col} =
\alpha/(d+1)$. In 2017 Kim proved the theorem with better function
$\beta_{col}$, which in particular tends to $1$ when $\alpha$ tends to $1$. Kim
also conjectured what is the optimal bound for $\beta_{col}(\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 optimal bounds also in more general setting when
we allow several sets of the same color.