×

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

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 \le i \le 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 \ge 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.

MSC:

52A35 Helly-type theorems and geometric transversal theory
52C45 Combinatorial complexity of geometric structures
05D15 Transversal (matching) theory
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)

References:

[1] Alon, N.; Bárány, I.; Füredi, Z.; Kleitman, DJ, Point selections and weak \(\varepsilon \)-nets for convex hulls, Comb. Probab. Comput., 1, 3, 189-200 (1992) · Zbl 0797.52004 · doi:10.1017/S0963548300000225
[2] Alon, N.; Kalai, G., Bounding the piercing number, Discrete Comput. Geom., 13, 3-4, 245-256 (1995) · Zbl 0826.52006 · doi:10.1007/BF02574042
[3] Alon, N.; Kalai, G.; Matoušek, J.; Meshulam, R., Transversal numbers for hypergraphs arising in geometry, Adv. Appl. Math., 29, 1, 79-101 (2002) · Zbl 1027.52003 · doi:10.1016/S0196-8858(02)00003-9
[4] Alon, N.; Kleitman, DJ, Piercing convex sets and the Hadwiger-Debrunner \((p, q)\)-problem, Adv. Math., 96, 1, 103-112 (1992) · Zbl 0768.52001 · doi:10.1016/0001-8708(92)90052-M
[5] Amenta, N.; De Loera, JA; Soberón, P.; Harrington, HA; Omar, M.; Wright, M., Helly’s theorem: new variations and applications, Algebraic and Geometric Methods in Discrete Mathematics. Contemporary Mathematics, 55-95 (2017), Providence: American Mathematical Society, Providence · Zbl 1383.52006
[6] Arocha, JL; Bárány, I.; Bracho, J.; Fabila, R.; Montejano, L., Very colorful theorems, Discrete Comput. Geom., 42, 2, 142-154 (2009) · Zbl 1173.52002 · doi:10.1007/s00454-009-9180-4
[7] Bárány, I., A generalization of Carathéodory’s theorem, Discrete Math., 40, 2-3, 141-152 (1982) · Zbl 0492.52005 · doi:10.1016/0012-365X(82)90115-7
[8] Bárány, I.; Matoušek, J.; Nešetřil, J.; Pellegrini, M., Tensors, colours, octahedra, Geometry, Structure and Randomness in Combinatorics. Centro di Ricerca Matematica Ennio De Giorgi (CRM) Series, 1-17 (2015), Pisa: Edizioni della Normale, Pisa · Zbl 1352.52007
[9] Boris, B.; Matoušek, J.; Gabriel, N., Lower bounds for weak epsilon-nets and stair-convexity, Isr. J. Math., 182, 1, 199-228 (2011) · Zbl 1222.68395 · doi:10.1007/s11856-011-0029-1
[10] Chazelle, B.; Edelsbrunner, H.; Grigni, M.; Guibas, L.; Sharir, M.; Welzl, E., Improved bounds on weak \(\epsilon \)-nets for convex sets, Discrete Comput. Geom., 13, 1, 1-15 (1995) · Zbl 0822.68110 · doi:10.1007/BF02574025
[11] Danzer, L., Über ein Problem aus der kombinatorischen Geometrie, Arch. Math. (Basel), 8, 5, 347-351 (1957) · Zbl 0078.35902 · doi:10.1007/BF01900144
[12] Danzer, L., Grünbaum, B., Klee, V.: Helly’s theorem and its relatives. In: 1963 Proceedings of the Symposium on Pure Mathematics, vol. VII, pp. 101-180. American Mathematical Society, Providence (1963) · Zbl 0132.17401
[13] Eckhoff, J.: Chapter: Helly, Radon, and Carathéodory type theorems. In: Handbook of Convex Geometry, pp. 389-448. Elsevier, Amsterdam (1990) · Zbl 0791.52009
[14] Goodman, J.E., Pollack, R., Wenger, R.: Chapter: geometric transversal theory. In: New Trends in Discrete and Computational Geometry, pp. 163-198. Springer, Berlin (1993) · Zbl 0792.52001
[15] Hadwiger, H.; Debrunner, H., Über eine Variante zum Helly’schen Satz, Arch. Math. (Basel), 8, 309-313 (1957) · Zbl 0080.15404 · doi:10.1007/BF01898794
[16] Helly, E., Über Mengen konvexer Körper mit gemeinschaftlichen Punkte, Jahresber. Dtsch. Math. Ver., 32, 175-176 (1923) · JFM 49.0534.02
[17] Holmsen, AF; Pach, J.; Tverberg, H., Points surrounding the origin, Combinatorica, 28, 6, 633-644 (2008) · Zbl 1199.52013 · doi:10.1007/s00493-008-2427-5
[18] Katchalski, M.; Liu, A., A problem of geometry in \(R^n\), Proc. Am. Math. Soc., 75, 2, 284-288 (1979) · Zbl 0418.52013
[19] Matoušek, J., Lectures on Discrete Geometry. Graduate Texts in Mathematics (2002), New York: Springer, New York · Zbl 0999.52006
[20] Rubin, N.: An improved bound for weak epsilon-nets in the plane. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 224-235 (2018). 10.1109/FOCS.2018.00030
[21] Santaló, L., Un teorema sobre conjuntos de paralelepípedos de aristas paralelas, Publ. Inst. Mat. Univ. Nacl Litoral, II, 4, 49-60 (1940)
[22] Wenger, R., Holmsen, A.: Chapter: Helly-type theorems and geometric transversals. In: Handbook of Discrete and Computational Geometry, 3rd edn, pp. 91-124. CRC Press LLC, Boca Raton (2017)
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.