×
Martínez-Sandoval, Leonardo; Roldán-Pensado, Edgardo; Rubin, Natan

Further consequences of the colorful Helly hypothesis. (English) Zbl 1491.52011

Speckmann, Bettina (ed.) et al., 34th international symposium on computational geometry, SoCG 2018, June 11–14, 2018, Budapest, Hungary. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 99, Article 59, 14 p. (2018).
Summary: Let \(\mathcal{F}\) be a family of convex sets in \(\mathbb{R}^d\), which are colored with \(d+1\) colors. We say that \(\mathcal{F}\) satisfies the Colorful Helly Property if every rainbow selection of \(d+1\) sets, one set from each color class, has a non-empty common intersection. The Colorful Helly Theorem of Lovász states that for any such colorful family \(\mathcal{F}\) there is a color class \(\mathcal{F}_i\subset\mathcal{F}\), for \(1\leq i\leq d+1\), whose sets have a non-empty intersection. We establish further consequences of the Colorful Helly hypothesis. In particular, we show that for each dimension \(d\geq 2\) there exist numbers \(f(d)\) and \(g(d)\) with the following property: either one can find an additional color class whose sets can be pierced by \(f(d)\) points, or all the sets in \(\mathcal{F}\) can be crossed by \(g(d)\) lines.
For the entire collection see [Zbl 1390.68027].

Cited in 2 Documents

MSC:

52A35 Helly-type theorems and geometric transversal theory

Keywords:

geometric transversals; convex sets; colorful Helly-type theorems; line transversals; weak epsilon-nets; transversal numbers
Cite Review PDF
Full Text: DOI

References:

[1] N. Alon, I. Bárány, Z. Füredi, and D. J. Kleitman. Point selections and weak ε-nets for convex hulls. Combinatorics Probability and Computing, 1(3):189-200, 1992. ##img## · Zbl 0797.52004
[2] N. Alon and G. Kalai. Bounding the piercing number. Discrete & Computational Geometry, 13(3):245-256, 1995. ##img## · Zbl 0826.52006
[3] N. Alon, G. Kalai, J. Matoušek, and R. Meshulam. Transversal numbers for hypergraphs arising in geometry. Advances in Applied Mathematics, 29(1):79-101, 2002. ##img## · Zbl 1027.52003
[4] N. Alon and D. J. Kleitman. Piercing convex sets and the Hadwiger-Debrunner (p, q)-problem. Advances in Mathematics, 96(1):103-112, 1992. ##img## · Zbl 0768.52001
[5] N. Amenta, J. A. De Loera, and P. Soberón. Helly’s Theorem: New Variations and Applications. Contemporary Mathematics, 685:55-95, 2017. URL: https://arxiv.org/abs/1508.07606. · Zbl 1383.52006
[6] J. L. Arocha, I. Bárány, J. Bracho, R. Fabila, and L. Montejano. Very colorful theorems. Discrete & Computational Geometry, 42(2):142-154, 2009. ##img## · Zbl 1173.52002
[7] I. Bárány. A generalization of Carathéodory’s theorem. Discrete Mathematics, 40(2-3):141-152, 1982. ##img## · Zbl 0492.52005
[8] I. Bárány. Tensors, colours, octahedra. In Geometry, Structure and Randomness in Combinatorics, pages 1-17. Springer, 2014. ##img## · Zbl 1352.52007
[9] L. Danzer. Über ein Problem aus der kombinatorischen Geometrie. Archiv der Mathematik, 8(5):347-351, 1957. ##img## · Zbl 0078.35902
[10] L. Danzer, B. Grünbaum, and V. Klee. Helly’s theorem and its relatives. Proceedings of symposia in pure mathematics: Convexity. American Mathematical Society, 1963. ##img## · Zbl 0132.17401
[11] J. Eckhoff. Handbook of Convex Geometry, chapter Helly, Radon, and Carathéodory type theorems, pages 389-448. Elsevier, 1990. ##img## · Zbl 0791.52009
[12] J. E. Goodman, R. Pollack, and R. Wenger. New Trends in Discrete and Computational Geometry, chapter Geometric Transversal Theory, pages 163-198. Springer Berlin Heidelberg, Berlin, Heidelberg, 1993. ##img## · Zbl 0792.52001
[13] H. Hadwiger and H. Debrunner. Über eine Variante zum Helly’schen Satz. Arch. Math., 8:309-313, 1957. ##img## · Zbl 0080.15404
[14] E. Helly. Über Mengen konvexer Körper mit gemeinschaftlichen Punkte. Jahresbericht der Deutschen Mathematiker-Vereinigung, 32:175-176, 1923. ##img## · JFM 49.0534.02
[15] A. F. Holmsen, J. Pach, and H. Tverberg. Points surrounding the origin. Combinatorica, 28(6):633-644, 2008. ##img## · Zbl 1199.52013
[16] M. Katchalski and A. Liu. A problem of geometry in Rⁿ. Proceedings of the American Mathematical Society, 75(2):284-288, 1979. ##img## · Zbl 0418.52013
[17] Leonardo Martínez-Sandoval, Edgardo Roldán-Pensado, and Natan Rubin. Further consequences of the colorful helly hypothesis. arXiv preprint, 2018. URL: https://arxiv.org/abs/1803.06229. · Zbl 1491.52011
[18] L. Santaló. Un teorema sobre conjuntos de paralelepípedos de aristas paralelas. Publicaciones del Instituto de Matemáticas, Universidad Nacional del Litoral, II(4):49-60, 1940. ##img##
[19] R. Wenger and A. Holmsen. The Handbook of Discrete and Computational Geometry, chapter Helly-type Theorems and Geometric Transversals, pages 91-124. Chapman and Hall/CRC, third edition edition, 2017. ##img##
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.