When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.19
URN: urn:nbn:de:0030-drops-138186
URL: https://drops.dagstuhl.de/opus/volltexte/2021/13818/
 Go to the corresponding LIPIcs Volume Portal

Optimal Bounds for the Colorful Fractional Helly Theorem

 pdf-format:

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 α ∈ (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.

BibTeX - Entry

```@InProceedings{bulavka_et_al:LIPIcs.SoCG.2021.19,
author =	{Bulavka, Denys and Goodarzi, Afshin and Tancer, Martin},
title =	{{Optimal Bounds for the Colorful Fractional Helly Theorem}},
booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
pages =	{19:1--19:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-184-9},
ISSN =	{1868-8969},
year =	{2021},
volume =	{189},
editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},