License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.40
URN: urn:nbn:de:0030-drops-138396
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13839/
Goaoc, Xavier ;
Holmsen, Andreas F. ;
Patáková, Zuzana
A Stepping-Up Lemma for Topological Set Systems
Abstract
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.
BibTeX - Entry
@InProceedings{goaoc_et_al:LIPIcs.SoCG.2021.40,
author = {Goaoc, Xavier and Holmsen, Andreas F. and Pat\'{a}kov\'{a}, Zuzana},
title = {{A Stepping-Up Lemma for Topological Set Systems}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {40:1--40:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13839},
URN = {urn:nbn:de:0030-drops-138396},
doi = {10.4230/LIPIcs.SoCG.2021.40},
annote = {Keywords: Helly-type theorem, Topological combinatorics, Homological minors, Stair convexity, Cubical complexes, Homological VC dimension, Ramsey-type theorem}
}
|
Keywords: |
|
Helly-type theorem, Topological combinatorics, Homological minors, Stair convexity, Cubical complexes, Homological VC dimension, Ramsey-type theorem |
|
Collection: |
|
37th International Symposium on Computational Geometry (SoCG 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.06.2021 |
