Bounding helly numbers via betti numbers

X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, M. Loebl, J. Nešetřil, R. Thomas (Eds.), A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, Springer, 2017, pp. 407–447.


Book Chapter | Published | English
Author
; ; ; ;
Book Editor
; ;
Department
Abstract
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 Rd such that βi(∩G)≤b for any G⊊F and every 0 ≤ i ≤ [d/2]-1 then F has Helly number at most h(b, d). Here βi denotes the reduced Z2-Betti numbers (with singular homology). These topological conditions are sharp: not controlling any of these [d/2] 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 C*(K)→C*(Rd).
Publishing Year
Date Published
2017-10-06
Book Title
A Journey through Discrete Mathematics: A Tribute to Jiri Matousek
Page
407 - 447
IST-REx-ID

Cite this

Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Bounding helly numbers via betti numbers. In: Loebl M, Nešetřil J, Thomas R, eds. A Journey through Discrete Mathematics: A Tribute to Jiri Matousek. A Journey Through Discrete Mathematics. Springer; 2017:407-447. doi:10.1007/978-3-319-44479-6_17
Goaoc, X., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2017). Bounding helly numbers via betti numbers. In M. Loebl, J. Nešetřil, & R. Thomas (Eds.), A Journey through Discrete Mathematics: A Tribute to Jiri Matousek (pp. 407–447). Springer. https://doi.org/10.1007/978-3-319-44479-6_17
Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Bounding Helly Numbers via Betti Numbers.” In A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, edited by Martin Loebl, Jaroslav Nešetřil, and Robin Thomas, 407–47. A Journey Through Discrete Mathematics. Springer, 2017. https://doi.org/10.1007/978-3-319-44479-6_17.
X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Bounding helly numbers via betti numbers,” in A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, M. Loebl, J. Nešetřil, and R. Thomas, Eds. Springer, 2017, pp. 407–447.
Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2017. Bounding helly numbers via betti numbers. A Journey through Discrete Mathematics: A Tribute to Jiri Matousek. A Journey Through Discrete Mathematics 407–447.
Goaoc, Xavier, et al. “Bounding Helly Numbers via Betti Numbers.” A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, edited by Martin Loebl et al., Springer, 2017, pp. 407–47, doi:10.1007/978-3-319-44479-6_17.

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Earlier Version

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search