DIMACS TR: 95-49
Ramsey-Type Results for Geometric Graphs
Authors: Gyula Karolyi, Janos Pach, Geza Toth
ABSTRACT
For any 2--coloring of the ${n \choose 2}$ segments determined by
$n$ points in general position in the plane, at least one of the
color classes contains a non-selfintersecting spanning tree.
Under the same assumptions, we also prove that there exist $[{{n+1} \over 3}]$
pairwise disjoint segments of the same color, and this bound is tight.
The above theorems were conjectured by Bialostocki and Dierker.
Furthermore, improving an earlier result of Larman et al., we construct
a family of $m$ segments in the plane, which has no more than
$m^{log 4/\log 27}$ members that are either pairwise disjoint of
pairwise crossing. Finally, we discuss some related problems and
generalizations.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-49.ps.gz
DIMACS Home Page