首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:Bounding Helly Numbers via Betti Numbers
  • 本地全文:下载
  • 作者:Xavier Goaoc ; Pavel Pat{\'a}k ; Zuzana Pat{\'a}kov{\'a
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2015
  • 卷号:34
  • 页码:507-521
  • DOI:10.4230/LIPIcs.SOCG.2015.507
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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 number at 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.
  • 关键词:Helly-type theorem; Ramsey's theorem; Embedding of simplicial complexes; Homological almost-embedding; Betti numbers
国家哲学社会科学文献中心版权所有