Document Open Access Logo

Further Consequences of the Colorful Helly Hypothesis

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.59.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Leonardo Martínez-Sandoval, Edgardo Roldán-Pensado, and Natan Rubin. Further Consequences of the Colorful Helly Hypothesis. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 59:1-59:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.59

Abstract

Let F be a family of convex sets in R^d, which are colored with d+1 colors. We say that 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 F there is a color class F_i subset F, for 1 <= i <= 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 >= 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 F can be crossed by g(d) lines.

Subject Classification

Keywords
  • geometric transversals
  • convex sets
  • colorful Helly-type theorems
  • line transversals
  • weak epsilon-nets
  • transversal numbers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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. Google Scholar
  2. N. Alon and G. Kalai. Bounding the piercing number. Discrete & Computational Geometry, 13(3):245-256, 1995. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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.
  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. Google Scholar
  7. I. Bárány. A generalization of Carathéodory’s theorem. Discrete Mathematics, 40(2-3):141-152, 1982. Google Scholar
  8. I. Bárány. Tensors, colours, octahedra. In Geometry, Structure and Randomness in Combinatorics, pages 1-17. Springer, 2014. Google Scholar
  9. L. Danzer. Über ein Problem aus der kombinatorischen Geometrie. Archiv der Mathematik, 8(5):347-351, 1957. Google Scholar
  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. Google Scholar
  11. J. Eckhoff. Handbook of Convex Geometry, chapter Helly, Radon, and Carathéodory type theorems, pages 389-448. Elsevier, 1990. Google Scholar
  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. Google Scholar
  13. H. Hadwiger and H. Debrunner. Über eine Variante zum Helly’schen Satz. Arch. Math., 8:309-313, 1957. Google Scholar
  14. E. Helly. Über Mengen konvexer Körper mit gemeinschaftlichen Punkte. Jahresbericht der Deutschen Mathematiker-Vereinigung, 32:175-176, 1923. Google Scholar
  15. A. F. Holmsen, J. Pach, and H. Tverberg. Points surrounding the origin. Combinatorica, 28(6):633-644, 2008. Google Scholar
  16. M. Katchalski and A. Liu. A problem of geometry in Rⁿ. Proceedings of the American Mathematical Society, 75(2):284-288, 1979. Google Scholar
  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.
  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. Google Scholar
  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. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact