DIMACS TR: 97-13
Ramsey-Type Results for Geometric Graphs. II
Authors: Gyula Karolyi, Janos Pach, Geza Toth, Pavel Valtr
ABSTRACT
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