License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.19
URN: urn:nbn:de:0030-drops-138186
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13818/
Go to the corresponding LIPIcs Volume Portal


Bulavka, Denys ; Goodarzi, Afshin ; Tancer, Martin

Optimal Bounds for the Colorful Fractional Helly Theorem

pdf-format:
LIPIcs-SoCG-2021-19.pdf (0.8 MB)


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},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13818},
  URN =		{urn:nbn:de:0030-drops-138186},
  doi =		{10.4230/LIPIcs.SoCG.2021.19},
  annote =	{Keywords: colorful fractional Helly theorem, d-collapsible, exterior algebra, d-representable}
}

Keywords: colorful fractional Helly theorem, d-collapsible, exterior algebra, d-representable
Collection: 37th International Symposium on Computational Geometry (SoCG 2021)
Issue Date: 2021
Date of publication: 02.06.2021


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI