---
_id: '1512'
abstract:
- lang: eng
  text: '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.'
acknowledgement: "PP, ZP and MT were partially supported by the Charles University
  Grant GAUK 421511. ZP was\r\npartially supported by the Charles University Grant
  SVV-2014-260103. ZP and MT were partially\r\nsupported by the ERC Advanced Grant
  No. 267165 and by the project CE-ITI (GACR P202/12/G061)\r\nof the Czech Science
  Foundation. UW was partially supported by the Swiss National Science Foundation\r\n(grants
  SNSF-200020-138230 and SNSF-PP00P2-138948). Part of this work was done when XG was
  affiliated with INRIA Nancy Grand-Est and when MT was affiliated with Institutionen
  för matematik, Kungliga Tekniska Högskolan, then IST Austria."
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Xavier
  full_name: Goaoc, Xavier
  last_name: Goaoc
- first_name: Pavel
  full_name: Paták, Pavel
  last_name: Paták
- first_name: Zuzana
  full_name: Patakova, Zuzana
  last_name: Patakova
  orcid: 0000-0002-3975-1683
- first_name: Martin
  full_name: Tancer, Martin
  last_name: Tancer
  orcid: 0000-0002-1191-6714
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: 'Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Bounding Helly numbers via
    Betti numbers. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2015:507-521. doi:<a href="https://doi.org/10.4230/LIPIcs.SOCG.2015.507">10.4230/LIPIcs.SOCG.2015.507</a>'
  apa: 'Goaoc, X., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2015). Bounding
    Helly numbers via Betti numbers (Vol. 34, pp. 507–521). Presented at the SoCG:
    Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SOCG.2015.507">https://doi.org/10.4230/LIPIcs.SOCG.2015.507</a>'
  chicago: Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner.
    “Bounding Helly Numbers via Betti Numbers,” 34:507–21. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2015. <a href="https://doi.org/10.4230/LIPIcs.SOCG.2015.507">https://doi.org/10.4230/LIPIcs.SOCG.2015.507</a>.
  ieee: 'X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Bounding Helly
    numbers via Betti numbers,” presented at the SoCG: Symposium on Computational
    Geometry, Eindhoven, Netherlands, 2015, vol. 34, pp. 507–521.'
  ista: 'Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2015. Bounding Helly numbers
    via Betti numbers. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34,
    507–521.'
  mla: Goaoc, Xavier, et al. <i>Bounding Helly Numbers via Betti Numbers</i>. Vol.
    34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 507–21, doi:<a
    href="https://doi.org/10.4230/LIPIcs.SOCG.2015.507">10.4230/LIPIcs.SOCG.2015.507</a>.
  short: X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2015, pp. 507–521.
conference:
  end_date: 2015-06-25
  location: Eindhoven, Netherlands
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2015-06-22
date_created: 2018-12-11T11:52:27Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2026-06-18T18:48:48Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SOCG.2015.507
file:
- access_level: open_access
  checksum: e6881df44d87fe0c2529c9f7b2724614
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:10:09Z
  date_updated: 2020-07-14T12:45:00Z
  file_id: '4794'
  file_name: IST-2016-501-v1+1_46.pdf
  file_size: 633712
  relation: main_file
file_date_updated: 2020-07-14T12:45:00Z
has_accepted_license: '1'
intvolume: '        34'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 507 - 521
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '5665'
pubrep_id: '501'
quality_controlled: '1'
related_material:
  record:
  - id: '424'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Bounding Helly numbers via Betti numbers
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2015'
...