Intersection patterns of planar sets

Kalai G, Patakova Z. 2020. Intersection patterns of planar sets. Discrete and Computational Geometry. 64, 304–323.

Download (ext.)

Journal Article | Published | English

Scopus indexed
Author
Kalai, Gil; Patakova, ZuzanaISTA
Department
Abstract
Let A={A1,…,An} be a family of sets in the plane. For 0≤i<n, denote by fi the number of subsets σ of {1,…,n} of cardinality i+1 that satisfy ⋂i∈σAi≠∅. Let k≥2 be an integer. We prove that if each k-wise and (k+1)-wise intersection of sets from A is empty, or a single point, or both open and path-connected, then fk+1=0 implies fk≤cfk−1 for some positive constant c depending only on k. Similarly, let b≥2, k>2b be integers. We prove that if each k-wise or (k+1)-wise intersection of sets from A has at most b path-connected components, which all are open, then fk+1=0 implies fk≤cfk−1 for some positive constant c depending only on b and k. These results also extend to two-dimensional compact surfaces.
Publishing Year
Date Published
2020-09-01
Journal Title
Discrete and Computational Geometry
Publisher
Springer Nature
Acknowledgement
We are very grateful to Pavel Paták for many helpful discussions and remarks. We also thank the referees for helpful comments, which greatly improved the presentation. The project was supported by ERC Advanced Grant 320924. GK was also partially supported by NSF grant DMS1300120. The research stay of ZP at IST Austria is funded by the project CZ.02.2.69/0.0/0.0/17_050/0008466 Improvement of internationalization in the field of research and development at Charles University, through the support of quality projects MSCA-IF.
Volume
64
Page
304-323
ISSN
eISSN
IST-REx-ID

Cite this

Kalai G, Patakova Z. Intersection patterns of planar sets. Discrete and Computational Geometry. 2020;64:304-323. doi:10.1007/s00454-020-00205-z
Kalai, G., & Patakova, Z. (2020). Intersection patterns of planar sets. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00205-z
Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.” Discrete and Computational Geometry. Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00205-z.
G. Kalai and Z. Patakova, “Intersection patterns of planar sets,” Discrete and Computational Geometry, vol. 64. Springer Nature, pp. 304–323, 2020.
Kalai G, Patakova Z. 2020. Intersection patterns of planar sets. Discrete and Computational Geometry. 64, 304–323.
Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.” Discrete and Computational Geometry, vol. 64, Springer Nature, 2020, pp. 304–23, doi:10.1007/s00454-020-00205-z.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Web of Science

View record in Web of Science®

Sources

arXiv 1907.00885

Search this title in

Google Scholar