Further Consequences of the Colorful Helly Hypothesis
- PDF / 639,064 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 46 Downloads / 220 Views
Further Consequences of the Colorful Helly Hypothesis Leonardo Martínez-Sandoval1,3 · Edgardo Roldán-Pensado2 · Natan Rubin1 Received: 28 June 2018 / Revised: 24 December 2018 / Accepted: 16 March 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract Let F be a family of convex sets in Rd , 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 Fi ⊂ 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. Keywords Geometric transversals · Convex sets · Colorful Helly-type theorems · Line transversals · Weak epsilon-nets · Transversal numbers Mathematics Subject Classification 52C17 · 52C35 · 52C45 · 05D15
Editor in Charge: Kenneth Clarkson Leonardo Martínez-Sandoval [email protected] Edgardo Roldán-Pensado [email protected] Natan Rubin [email protected] 1
Department of Computer Science, Ben-Gurion University of the Negev, 84105 Beer-Sheva, Israel
2
Centro de Ciencias Matemáticas, UNAM campus Morelia, 58190 Morelia, Michoacán, Mexico
3
Present Address: Institut de Mathématiques de Jussieu - Paris Rive Gauche (UMR 7586), 4 Place Jussieu, 75252 Paris Cedex 5, France
123
Discrete & Computational Geometry
1 Introduction 1.1 Helly-Type Theorems Let F be a finite family of convex sets in Rd . We say that a collection X of geometric objects (e.g., points, lines, or k-flats—k-dimensional affine subspaces of Rd ) is a transversal to F, or that F can be pierced or crossed by X , if each set of F is intersected by some member of X . For an integer j we use the symbol Fj to denote the collection of subfamilies of F of size j. The 1913 theorem of Helly [16] states that a finite family F of convex sets has a non-empty intersection (i.e., F can be pierced by a single point) if and only if each of its subsets F ⊂ F of size at most d + 1 can be pierced by a point. In the past 50 years Geometric Transversal Theory has been preoccupied with the following questions (see e.g. [5,12–14,22]): • Does Helly’s Theorem generalize to transversals by k-flats, for 1 ≤ k ≤ d − 1? F have a non-empty • Given that a significant fraction of the (d +1)-tuples F ∈ d+1 intersection, can F, or at least some fixed fraction of its members, be pierced by constantly many points? The first question has been settled to the negative already for k = 1. For instance, Santaló [21] and Danzer [11] observed that for any n ≥ 3 there are families F of n convex sets in R2 such that any n − 1 of the sets can be crossed by a single line transversal
Data Loading...
