A Stepping-Up Lemma for Topological Set Systems
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
A Stepping-Up Lemma for Topological Set Systems
Original language description
Intersection patterns of convex sets in Rd have the remarkable property that for d+1<=k<=ℓ, 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
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
Leibniz International Proceedings in Informatics, LIPIcs
ISBN
978-3-95977-184-9
ISSN
1868-8969
e-ISSN
—
Number of pages
17
Pages from-to
1-17
Publisher name
Schloss Dagstuhl
Place of publication
Německo
Event location
USA
Event date
Jun 7, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—