Optimal bounds for the colorful fractional Helly theorem

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Optimal bounds for the colorful fractional Helly theorem

Popis výsledku v původním jazyce

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&apos;s conjecture by extending Kalai&apos;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.

Název v anglickém jazyce

Optimal bounds for the colorful fractional Helly theorem

Popis výsledku anglicky

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&apos;s conjecture by extending Kalai&apos;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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 37th International Symposium on Computational Geometry (SoCG 2021)

ISBN

978-3-95977-184-9

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

14

Strana od-do

1-14

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum für Informatik

Místo vydání

Dagstuhl, Germany

Místo konání akce

online

Datum konání akce

7. 6. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—