RAMSEY-TYPE RESULTS FOR GEOMETRIC GRAPHS, II

We show that for any two-coloring of the ((n)(2)) segments determined by n points in the plane, one of the color classes contains noncrossin g cycles of lengths 3, 4,..., [root n/2]. This result is tight up to a multiplicative constant. Under the same assumptions, we also grove th at there is a noncrossing path of length Omega(n(2/3)), all of whose e dges are of the same color. In the special case when the n points are in convex position, we find longer monochromatic noncrossing paths, of length [(n + 1)/2]. This bound cannot be improved. We also discuss so me related problems and generalizations. In particular, we give sharp estimates for the largest number of disjoint monochromatic triangles t hat can always be selected from our segments.