2026-07-23T21:52:40Z https://drops.dagstuhl.de/oai

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

A Stepping-Up Lemma for Topological Set Systems Goaoc, Xavier Holmsen, Andreas F. Patáková, Zuzana Helly-type theorem Topological combinatorics Homological minors Stair convexity Cubical complexes Homological VC dimension Ramsey-type theorem Intersection patterns of convex sets in ℝ^d have the remarkable property that for d+1 ≤ k ≤ 𝓁, in any sufficiently large family of convex sets in ℝ^d, 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 ℱ in ℝ^d. Quantitatively, our bounds depend on how complicated the intersection of 𝓁 elements of ℱ can be, as measured by the maximum of the ⌈d/2⌉ 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 Nivasch to recast a simplicial complex as a homological minor of a cubical complex. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xavier Goaoc and Andreas F. Holmsen and Zuzana Patáková 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.40 urn:nbn:de:0030-drops-138396 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.40 eng https://creativecommons.org/licenses/by/4.0/legalcode