DIMACS TR: 97-13

Ramsey-Type Results for Geometric Graphs. II

Authors: Gyula Karolyi, Janos Pach, Geza Toth, Pavel Valtr


We show that for any 2--coloring of the ${n \choose 2}$ segments determined by $n$ points in the plane, one of the color classes contains non-crossing cycles of lengths $3,4,\ldots,\lfloor\sqrt{n/2}\rfloor$. This result is tight up to a multiplicative constant. Under the same assumptions, we also prove that there is a non-crossing path of length $\Omega(n^{2/3})$, all of whose edges are of the same color. In the special case when the $n$ points are in convex position, we find longer monochromatic non-crossing paths, of length $\lceil\frac{n+1}{2}\rceil$. This bound cannot be improved. We also discuss some related problems and generalizations. In particular, we give sharp estimates for the largest number of disjoint monochromatic triangles that can always be selected from our segments.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-13.ps.gz
DIMACS Home Page