Bounding Helly numbers via Betti numbers
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10312213" target="_blank" >RIV/00216208:11320/15:10312213 - isvavai.cz</a>
Result on the web
<a href="http://drops.dagstuhl.de/opus/volltexte/2015/5129/" target="_blank" >http://drops.dagstuhl.de/opus/volltexte/2015/5129/</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.SOCG.2015.507" target="_blank" >10.4230/LIPIcs.SOCG.2015.507</a>
Alternative languages
Result language
angličtina
Original language name
Bounding Helly numbers via Betti numbers
Original language description
We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^d such that the ith reduced Betti number (with Z_2 coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every non-negative integer i less or equal to (d-1)/2, then F has Helly numberat most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2015
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
Proceedings of the 31st International Symposium on Computational Geometry (SoCG 2015)
ISBN
978-3-939897-83-5
ISSN
—
e-ISSN
—
Number of pages
15
Pages from-to
507-521
Publisher name
LIPICS
Place of publication
Dagstuhl
Event location
Eindhoven
Event date
Jun 22, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—