2026-08-03T22:30:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13818 2024-03-06T10:52:47Z ddc:004 open_access

Optimal Bounds for the Colorful Fractional Helly Theorem Bulavka, Denys Goodarzi, Afshin Tancer, Martin colorful fractional Helly theorem d-collapsible exterior algebra d-representable 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Denys Bulavka and Afshin Goodarzi and Martin Tancer 2021 Is Part Of LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2021.19 urn:nbn:de:0030-drops-138186 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.19 eng https://creativecommons.org/licenses/by/4.0/legalcode