Optimal bounds for the colorful fractional Helly theorem
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10430555" target="_blank" >RIV/00216208:11320/21:10430555 - isvavai.cz</a>
Result on the web
<a href="https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=13818" target="_blank" >https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=13818</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2021.19" target="_blank" >10.4230/LIPIcs.SoCG.2021.19</a>
Alternative languages
Result language
angličtina
Original language name
Optimal bounds for the colorful fractional Helly theorem
Original language description
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 α ELEMENT OF (0, 1] and every non-negative integer d, there is β_{col} = β_{col}(α, d) ELEMENT OF (0, 1] with the following property. Let ℱ1, ... , ℱ_{d+1} be finite nonempty families of convex sets in ℝ^d of sizes n1, ... , n_{d+1}, respectively. If at least α n1 n1 MIDLINE HORIZONTAL ELLIPSIS n_{d+1} of the colorful (d+1)-tuples have a nonempty intersection, then there is i ELEMENT OF [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 (F1, ... , 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 37th International Symposium on Computational Geometry (SoCG 2021)
ISBN
978-3-95977-184-9
ISSN
1868-8969
e-ISSN
—
Number of pages
14
Pages from-to
1-14
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum für Informatik
Place of publication
Dagstuhl, Germany
Event location
online
Event date
Jun 7, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—