A Stepping-Up Lemma for Topological Set Systems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10438435" target="_blank" >RIV/00216208:11320/21:10438435 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.4230/LIPIcs.SoCG.2021.0" target="_blank" >https://doi.org/10.4230/LIPIcs.SoCG.2021.0</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2021.0" target="_blank" >10.4230/LIPIcs.SoCG.2021.0</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Stepping-Up Lemma for Topological Set Systems

Popis výsledku v původním jazyce

Intersection patterns of convex sets in Rd have the remarkable property that for d+1&lt;=k&lt;=ℓ, in any sufficiently large family of convex sets in Rd, if a constant fraction of the k-element subfamilies have nonempty intersection, then a constant fraction of the ℓ-element subfamilies must also have nonempty intersection. Here, we prove that a similar phenomenon holds for any topological set system F in Rd. Quantitatively, our bounds depend on how complicated the intersection of ℓ elements of F can be, as measured by the sum of the LEFT CEILINGd2RIGHT CEILING first Betti numbers. As an application, we improve the fractional Helly number of set systems with bounded topological complexity due to the third author, from a Ramsey number down to d+1. We also shed some light on a conjecture of Kalai and Meshulam on intersection patterns of sets with bounded homological VC dimension. A key ingredient in our proof is the use of the stair convexity of Bukh, Matoušek and Nivash to recast a simplicial complex as a homological minor of a cubical complex.

Název v anglickém jazyce

A Stepping-Up Lemma for Topological Set Systems

Popis výsledku anglicky

Intersection patterns of convex sets in Rd have the remarkable property that for d+1&lt;=k&lt;=ℓ, in any sufficiently large family of convex sets in Rd, if a constant fraction of the k-element subfamilies have nonempty intersection, then a constant fraction of the ℓ-element subfamilies must also have nonempty intersection. Here, we prove that a similar phenomenon holds for any topological set system F in Rd. Quantitatively, our bounds depend on how complicated the intersection of ℓ elements of F can be, as measured by the sum of the LEFT CEILINGd2RIGHT CEILING first Betti numbers. As an application, we improve the fractional Helly number of set systems with bounded topological complexity due to the third author, from a Ramsey number down to d+1. We also shed some light on a conjecture of Kalai and Meshulam on intersection patterns of sets with bounded homological VC dimension. A key ingredient in our proof is the use of the stair convexity of Bukh, Matoušek and Nivash to recast a simplicial complex as a homological minor of a cubical complex.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-184-9

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

17

Strana od-do

1-17

Název nakladatele

Schloss Dagstuhl

Místo vydání

Německo

Místo konání akce

USA

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

—