Further consequences of the colorful Helly hypothesis

DOI10.1007/S00454-019-00085-YMaRDI QIDQ2189733zbMATH OpenOpenAlexWikidataFDO

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

Publication date 16 June 2020

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.06229, https://drops.dagstuhl.de/opus/volltexte/2018/8772/

zbMATH Keywords

colorful Helly-type theoremsconvex setsgeometric transversalsline transversalstransversal numbersweak epsilon-nets

Mathematics Subject Classification ID

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

Abstract: Let $mathcalF$ be a family of convex sets in ${mathbbR}^d$, which are colored with $d+1$ colors. We say that $mathcalF$ 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'asz states that for any such colorful family $mathcalF$ there is a color class $mathcal{F}_{i}subsetmathcalF$, for $1leqileqd+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 $dgeq2$ 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 $mathcalF$ can be crossed by $g(d)$ lines.

Recommendations

• Further consequences of the colorful Helly hypothesis
• Colored coalescent theory
• Coloring Theories
• The Helmholtz legacy in color metrics: Schrödinger's color theory
• scientific article; zbMATH DE number 572142
• The colourful feasibility problem
• scientific article; zbMATH DE number 3961642
• Defective coloring revisited
• scientific article; zbMATH DE number 932605

Cites work

• A generalization of Caratheodory's theorem
• A Problem of Geometry in R n
• Bounding the piercing number
• Helly’s theorem: New variations and applications
• scientific article; zbMATH DE number 431990 (Why is no real title available?)
• scientific article; zbMATH DE number 480237 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 3214278 (Why is no real title available?)
• Improved bounds on weak \(\varepsilon\)-nets for convex sets
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Point Selections and Weak ε-Nets for Convex Hulls
• Points surrounding the origin
• Tensors, colours, octahedra
• Transversal numbers for hypergraphs arising in geometry
• Very colorful theorems
• Über ein Problem aus der kombinatorischen Geometrie
• Über eine Variante zum Hellyschen Satz

Cited in

(11)

• Colourful and fractional \((p,q)\)-theorems
• A note on the colorful fractional Helly theorem
• The colorful Helly theorem and general hypergraphs
• Further consequences of the colorful Helly hypothesis
• Transversals, topology and colorful geometric results
• Helly-type problems
• Discrete geometry. Abstracts from the workshop held January 21--26, 2024
• Some new results on geometric transversals
• Colorful intersections and Tverberg partitions
• Transversals to colorful intersecting convex sets
• Piercing intersecting convex sets

This page was built for publication: Further consequences of the colorful Helly hypothesis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189733)