Separated matchings on colored convex sets
Viola Mészáros · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2010
Erdős posed the following problem. Consider an equicolored point set of 2n points, n points red and n points blue, in the plane in convex position. We estimate the minimal number of points on the longest noncrossing path such that edges join points of different color and are straight line segments. The upper bound 4 3 n + O( √ n) is proved [7], [5] and is conjectured to be tight. The best known lower bound is n+Ω( √ n) [5]. A separated matching is a matchings where no two edges cross geometrically and all edges can be crossed by a line. Here we give a class of configurations that allows at most 4 3 n + O( √ n) points in the maximum separated matching. This underlines the importance of the separated matching conjecture [7], [5]. We also present a type of coloring such that the optimal coloring allows at most 4 3 n + O( √ n) points in maximum separated matching. On the other hand, if the discrepancy (that is, the maximum difference in cardinality of color classes in any interval of consecutive points) is two or three, we show that the number of vertices in the maximum separated matching is at least 4 3 n.