
\documentstyle{article}

\sloppy
\textwidth=115mm
\textheight=175mm
\addtolength{\oddsidemargin}{-3cm}
\addtolength{\topmargin}{-3cm}

\def\newpic#1{%
   \def\emline##1##2##3##4##5##6{%
      \put(##1,##2){\special{em:point #1##3}}%
      \put(##4,##5){\special{em:point #1##6}}%
      \special{em:line #1##3,#1##6}}}

\newpic{}

\def\el(#1, #2)(#3, #4){\emline{#1}{#2}{1}{#3}{#4}{2}}

\def\ax{0.975} \def\ay{-0.2224}
\def\bx{0.7818} \def\by{-0.6234}
\def\cx{0.4338} \def\cy{-0.9}
\def\dx{0} \def\dy{-1}
\def\ex{-0.4338} \def\ey{-0.9}
\def\fx{-0.7818} \def\fy{-0.6234}
\def\gx{-0.975} \def\gy{-0.2224}
\def\hx{-0.975} \def\hy{0.2224}
\def\ix{-0.7818} \def\iy{0.6234}
\def\jx{-0.4338} \def\jy{0.9}
\def\kx{0} \def\ky{1}
\def\lx{0.4338} \def\ly{0.9}
\def\mx{0.7818} \def\my{0.6234}
\def\nx{0.975} \def\ny{0.2224}


\title{Ramsey--Type Results for Geometric Graphs. II}

\author{{\sl Gyula K\'arolyi}\thanks{Supported by NSF grant DMS-9304580,
the Alfred Sloan Foundation, and DIMACS under NSF grant STC-91-19999.}\\
\ \ \ \ \ E\"otv\"os University, Budapest\\
          and ETH Z\"urich\ \ \ \ \  \\
\and
{\sl J\'anos Pach}\thanks{Supported by NSF grant
CCR-94-24398,
PSC-CUNY Research Award 663472, and OTKA-T-020914.}\\
City College, CUNY and\\
Courant Institute, NYU\\
\and
{\sl G\'eza T\'oth}\thanks{Supported by OTKA-14220, OTKA-T-020914, and the
Alfred Sloan Foundation.}\\
Courant Institute, NYU \\
\and
{\sl Pavel Valtr}\thanks{Supported by the Czech Republic grant
GA\v CR 0194, Charles University grants GAUK 193/1996 and 194/1996,
and by DIMACS Center.}\\
Charles University, Prague and\\
DIMACS Center, Rutgers University}




\date{}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}

\def\u{{\cal U}}
\def\rect{{\rm Rect}}
\def\q#1#2{Q^{#1#2}}


\begin{document}
\maketitle

\begin{abstract}
\noindent 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. 
%All of these cycles and paths can be found by $O(n^2)$ time algorithms. 
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.
\end{abstract}




\section{Introduction}



A {\em geometric graph} is a graph drawn in the plane so that every
vertex corresponds to a point, and every edge is a closed straight-line
segment connecting two vertices but not passing through a third.
The ${n \choose 2}$ segments determined by $n$ points in the plane,
no three of which are collinear, form a {\em complete} geometric
graph with $n$ vertices  (see [PA95]). In classical Ramsey theory, we
want to find large monochromatic subgraphs in a complete graph whose
edges are colored with several colors [B74], [GRS90]. Most questions
of this type can be formulated for complete geometric graphs, where
the monochromatic subgraphs are required to satisfy certain geometric
conditions. The investigation of these problems was
initiated in [KPT96].

A subgraph of a geometric graph is said to be {\em
non-crossing}, if no two of its edges have an interior point
in common. In the present paper, we show how to
find large non-crossing monochromatic paths and cycles in a
geometric graph whose edges are colored with two colors.

\begin{theorem}\label{1.1}
For any $2$--coloring of the edges of a complete geometric
graph with $n$ vertices, there exist non-crossing cycles of
length $3, 4,\ldots,\lfloor\sqrt{n/2}\rfloor$, all of whose edges are of
the same color. The order of magnitude of this bound cannot
be improved.
\end{theorem}

\begin{theorem}\label{1.2}
For any $2$--coloring of the edges of a complete geometric
graph with $n$ vertices, there exists a non-crossing path of
length $\Omega(n^{2/3})$, all of whose edges are of the same
color.
\end{theorem}

The last result improves the bound $\Omega(n^{1/2})$ established in [KPT96].
It is very likely that the $\Omega(n^{2/3})$ bound in Theorem \ref{1.2}
can be further improved to (nearly) linear. We can verify
this conjecture for {\em convex geometric graphs}, i.e., for
geometric graphs whose $n$ points form the vertex set of a
convex polygon.

\begin{theorem}\label{1.3}
For any $2$--coloring of the edges of a complete convex
geometric graph with $n\geq 3$ vertices, there exists a
non-crossing monochromatic path of length $\lfloor\frac{n+1}{2}\rfloor$.
This bound cannot be improved.
\end{theorem}

The proof of Theorem \ref{1.3} uses the following
unpublished result of Micha Perles, whose proof is included.

\begin{theorem}\label{1.4}
{\bf (Perles)} If a convex geometric graph of $n\geq k+1$ vertices
has more than
$\lfloor (k-1)n/2 \rfloor$ edges than it contains a non-crossing
path of length $k$. This bound cannot be improved.
\end{theorem}

A graph is called a {\em caterpillar}, if it is a tree containing no
three edge disjoint paths of length two starting at the same vertex.
In fact,
Perles proved that under the conditions of Theorem~\ref{1.4}, one can
always find a
non-crossing subgraph isomorphic to any given caterpillar of
$k+1$ vertices.

The proofs of Theorems~\ref{1.1}-\ref{1.4} can be turned into $O(n^2)$ time
algorithms to find monochromatic cycles resp. paths
with the required properties.

The above results can be rephrased using the following
notation. Let ${\cal G}$ be a class of (so-called {\em
forbidden}) geometric subgraphs. We want to determine the
smallest number $R=R\left( {\cal G}\right)$ with the
property that every complete geometric graph with $R$
vertices, whose edges are colored with 2 colors, contains a
monochromatic subgraph belonging to ${\cal G}$. If we restrict our
attention to {\em convex} geometric graphs, then the
corresponding function is denoted by $R_c\left( {\cal
G}\right)$.
Clearly, $R_c\left( {\cal G}\right)\le R\left( {\cal G}\right)$.

For any positive integer $k$,
let $k{\cal G}$ denote the class of all geometric graphs
that can be obtained by taking the union of $k$ pairwise
disjoint members of ${\cal G}$, any two of which can be
separated by a straight line.

\begin{theorem}\label{1.5}
Let ${\cal G}$ be any class of geometric graphs, each of
which has at least two vertices.

{\mbox {\bf (i)}} If $k$ is a power of $2$ then
$$R(k{\cal G}) \leq (R({\cal G})+1)k-1.$$

{\mbox {\bf (ii)}} For any $k>0$
$$R(k{\cal G}) \leq \left\lceil {3(R({\cal G})+1)\over 2}\right\rceil k -
\left\lceil {R({\cal G})+1\over 2}\right\rceil .$$

{\mbox {\bf (iii)}} For any $k>0$
$$R_c(k{\cal G}) \leq (R_c({\cal G})+1)k-1.$$
\end{theorem}

In particular, if ${\cal G}={\cal T}$ is the class of triangles,
we have $R({\cal T})=6$. Thus, by Theorem \ref{1.5} (i), we
obtain
$$R(k{\cal T}) \leq 7k-1,$$
provided that $k$ is a power of 2.  The following theorem
shows that this result cannot be
improved.

\begin{theorem}\label{1.6} Let ${\cal T}$ denote the class of triangles
and let $k$ be a positive integer.
Then
$$R_{\Delta}(k):=R(k{\cal T})\ge (R({\cal T})+1)k-1=7k-1\ .$$
\end{theorem}

Using the approach of [KPTT97], one can design an
$O(n^{\log\log n+2})$-time algorithm to find
$k$ pairwise {\em non-crossing}
triangles of the same color in any complete geometric graph of $n=7k-1$
vertices,
whose edges are colored with two colors, provided that $k$ is a power of $2$.
(Note that in an abstract graph, one can always find 
$\lfloor n/5 \rfloor$ pairwise {\em vertex-disjoint}
triangles of the same color [BES75].) 


The paper is organized as follows. Sections 2 and 3 contain the proofs
of Theorems~\ref{1.1} and \ref{1.2}, respectively. Theorems~\ref{1.3}
and \ref{1.4} are proved in Section 4, while  Sections 5 and 6 contain
the proofs of Theorems~\ref{1.5} and \ref{1.6}, resp.
%At the end of each section, we give an efficient algorithm to find a subgraph with the properties guaranteed by the corresponding theorem(s).



\section{Cycles -- Proof of Theorem~\ref{1.1}}


Theorem~\ref{1.1} is an immediate consequence of the following result.

\begin{theorem}\label{c}
Let ${\cal C}_k$ be the class of all
non-crossing cycles of length $k$, and let
let ${\cal D}_k$ be the class of all
non-crossing cycles of length $k$, triangulated from
a vertex. Then
$$\Omega(k^2)= R_c({\cal C}_k)\le R({\cal C}_k)\le  R({\cal D}_k)=O(k^2).$$
\end{theorem}

\noindent {\bf Proof.} First we prove that $R_c({\cal C}_k)> (k-1)^2$.

Take $(k-1)^2$ points on a circle and partition them into $k-1$ groups,
each containing $k-1$ consecutive points.
Color with red  all edges between
points in different groups, and color with blue all edges between
points belonging to the same group.

Any red non-crossing cycle contains at most one point from each group,
hence it can not have more than $k-1$ points.
On the other hand, all vertices of a blue cycle are from the same
group, so there is no blue cycle with more than $k-1$ points.

Next we show that $R({\cal D}_k)\le 2(k-1)(k-2)+2$.

Let $P$ denote the vertex set of a complete geometric graph $G$
of $2(k-1)(k-2)+2$ vertices, whose edges are colored with red and blue.
Let $p$ be a vertex of the convex hull of $P$. Since there are
$2(k-1)(k-2)+1$ edges incident to $p$, at least $(k-1)(k-2)+1$ of them
are of the same color, say, red.
Let $p_1, p_2, \ldots, p_{(k-1)(k-2)+1}$ be vertices of $G$,
listed in clockwise order of visibility from $p$,
such that each edge $pp_i$ is red.
A path $p_{i_1}p_{i_2}\ldots p_{i_j}$ is said to be {\em monotone}
if $i_1<i_2<\ldots <i_j$.


Define a partial ordering of the vertices   
$p_1, p_2,$  $\ldots, p_{(k-1)(k-2)+1}$, as follows.
Let $p_i < p_j$ if $i < j$ and there
is a monotone red path connecting $p_i$ to $p_j$.
By Dilworth's theorem [D50], there are either
$k-1$ elements that form a totally ordered subset,
or $k$ elements that are pairwise incomparable.
In the first case, there is a monotone red path $q_1, q_2, \ldots, q_{k-1}$
and we can complete it to a non-crossing red cycle
$p, q_1, q_2, \ldots, q_{k-1}$ of size $k$, together with the corresponding
diagonals from $p$.
In the second case, there is a complete blue subgraph of $k$
vertices $q_1, q_2, \ldots, q_k$ because any two incomparable elements
are connected by a blue edge. By a result of Gritzmann et al. [GMPP91, PA95],
this contains a non-crossing
cycle of length $k$, triangulated from
a vertex. $\Box$

%\smallskip

%\noindent {\bf Algorithm.}
%Based on this proof, in any 2-colored complete geometric graph of
%$n=2(k-1)(k-2)+2$ vertices, one can find a monochromatic non-crossing
%cycle of length $k$, triangulated from a vertex, in $O(k^4)=O(n^2)$ time.
%We sketch the algorithm, using the notation in the above proof.

%\begin{itemize}

%\item[1.] Find the vertices $p$, $p_1, p_2, \ldots, p_{(k-1)(k-2)+1}$.
%[This requires $O(k^2\log k)$ steps.]

%\item[2.] Build a data-structure to store for each vertex $p_i$
%the longest clockwise monotone red path on
%$\{ p_1, p_2, \ldots, p_i\}$ ending at $p_i$, together with its length
%$r_i$ ($i=1, 2, \ldots, (k-1)(k-2)+1$).
%[$O(k^4)$ steps.]

%\item[3.] Check if there is any $r_i\ge k-2$. If yes, then return the
%corresponding  non-crossing red
%cycle of length $k$, triangulated from $p$. [$O(k^2)$ steps.]

%\item[4.] If all $r_i< k-2$,  then find $k$ vertices
%$p_{i_1}, p_{i_2}, \ldots, p_{i_k}$ such that
%$r_{i_1}= r_{i_2}= \ldots = r_{i_k}$. Return a non-crossing blue
%cycle of length $k$, triangulated from a vertex, induced by
%$\{ p_{i_1}, p_{i_2}, \ldots, p_{i_k}\}$. [$O(k^2\log k)$ steps.]

%\end{itemize}


\section{Paths -- Proof of Theorem~\ref{1.2}}

Let $G$ be a complete geometric graph whose
edges are colored red and blue. Suppose that $G$
contains no monochromatic non-crossing path of length $m$.
To establish Theorem~\ref{1.2}, it is enough to prove that $G$ has
at most $O(m^{3/2})$ vertices.

Suppose without loss of generality that no two vertices lie on a vertical line.
For each vertex $v$ of $G$, let $b(v)$ (resp. $r(v)$) denote the length
of the longest $x$-monotone blue path (resp. red) in $G$ whose rightmost
vertex is $v$.

Since every monotone path is non-crossing,
$b(v)$ and $r(v)$ are integers
between $0$ and $m-1$.
Observe that $(b(v), r(v))\ne (b(v'),r(v'))$ for $v\ne v'$.
Indeed, if $v\ne v'$ are two vertices of $G$ such that $v'$ lies
to the right of $v$, then $b(v')>b(v)$ (if $vv'$ is colored blue)
or $r(v')>r(v)$ (if $vv'$ is colored red). As a consequence,
$G$ has at most $m^2$ vertices. The following more careful analysis
gives a better bound.

Define $\u$ as the set of pairs
with $(b,r)=(b(u),r(u))$ for some vertex $u$ of $G$.
For $0\le b_1\le b_2\le m$ and $0\le r_1\le r_2\le m$,
define a subset $\rect(b_1,b_2,r_1,r_2)$ of $\u$ by
$$\rect(b_1,b_2,r_1,r_2)=\{(b,r)\in\u\ |\ b_1\le b<b_2, r_1\le r<r_2\}.$$
Every pair $(b,r)$, $0\le b\le m$, $0\le r\le m$, defines a partition
of $\u$ into the following four subsets:
\begin{eqnarray*} 
\q++(b,r) & = \rect(b,m,r,m),\ \ \ \ \  \q+-(b,r) & = \rect(b,m,0,r),\\
\q-+(b,r) & = \rect(0,b,r,m),\ \ \ \ \  \q--(b,r) & = \rect(0,b,0,r).
\end{eqnarray*}
The key observation is the following.

\begin{lemma}\label{lin}
For any $t\in\{1,2,\dots,2m-1\}$, there are two integers
$b(t),r(t)\in\{0,1,\dots,m\}$ such that $b(t)+r(t)=t$
and
$$|\q+-(b(t),r(t))\cup\q-+(b(t),r(t))|\le 3m.$$
\end{lemma}

Before giving the proof of Lemma~\ref{lin}, we finish the proof
of Theorem~\ref{1.2}. Obviously, it suffices to show that
$|\u|=O(m^{3/2})$.

Suppose for simplicity that $s=\sqrt{2m}$ is an integer.
Somewhat inaccurately, we shorten the
notation $\q++(b(t),r(t))$ to $\q++(t)$. We also shorten
$\q+-(b(t),r(t))$, $\q-+(b(t),r(t))$, and $\q--(b(t),r(t))$
analogously. We have
$$\u= \bigcup_{t=s,2s,\dots,s^2-s} \left(\q+-(t)\cup\q-+(t)\right)
\cup \bigcup_{t=0,s,2s,\dots,s^2-s} \left(\q++(t)\cap\q--(t+s)\right),$$ 

\noindent because each pair $(b,r)\in\u$ with
$ks\le b+r<(k+1)s$ lies in the first union (in a term with
$t=ks$ or with $t=(k+1)s$)
or in the term $\q++(ks)\cap\q--(ks+s)$ of the second
union. Consequently,
$$|\u|  \le \sum_{t=s,2s,\dots,s^2-s} \left|\q+-(t)\cup\q-+(t)\right|
 + \sum_{t=0,s,2s,\dots,s^2-s} \left|\q++(t)\cap\q--(t+s)\right|.$$ 

By Lemma~\ref{lin}, each term in the first sum is at most $3m$,
and it is easy to check that each term in the second sum is at most
%${s\over2}\cdot{s\over2}={m\over 2}$. 
$(s/2)^2=m/2$.
It follows that
$$|\u| \le  (s-1)\cdot 3m+s{m\over 2} = O(m^{3/2}).\ \ \Box$$

It remains to prove Lemma~\ref{lin}.
\bigskip

\noindent{\bf Proof of Lemma~\ref{lin}.}
Suppose without loss of generality that $t\le m$.
For each $b=0,1,\dots,t$, denote
$$\Delta(b)=|\q-+(b,t-b)|-|\q+-(b,t-b)|.$$
It follows from
$$\Delta(0)\le 0\le\Delta(m)$$
\noindent and from
$$|\Delta(b+1)-\Delta(b)|
=|\rect(b,b+1,0,m)|+|\rect(0,m,t-b-1,t-b)|
\le $$ $$ \le m+m=2m$$
\noindent that there is a $b_0\in\{0,\dots,m\}$ with
$$|\Delta(b_0)|\le m.$$

We now show that the lemma holds with $b(t)=b_0$ and $r(t)=t-b_0$.
Suppose this is not true, i.e.,
$$|\q+-(t)|+|\q-+(t)|\ge 3m+1. $$
Then $|\Delta(b(t))|\le m$ gives
$$|\q+-(t)|\ge m+1,\ \ \ \ \ |\q-+(t)|\ge m+1.$$
Consequently, there is a vertical line $\ell$ such that
a set $V_1$ of at least $m+1\over 2$ vertices
to the left of $\ell$ corresponds to a subset of
$\q+-(t)$ or  $\q-+(t)$,
and a set $V_2$ of at least $m+1\over 2$ vertices
to the right of $\ell$ corresponds to a subset of
$\q-+(t)$ or $\q+-(t)$, respectively.
All edges of the complete bipartite geometric graph
$(V_1\cup V_2,V_1\times V_2)$ are colored by the same color:
red, if $V_1$ corresponds to elements of
$\q+-(t)$, and blue, otherwise. It is well-known (e.g., see [AGHN97]) that
if $V_1$, $|V_1|\ge {m+1\over 2}$, is separated by a line from $V_2$,
$|V_2|\ge {m+1\over 2}$, then the  graph
$(V_1\cup V_2,V_1\times V_2)$ contains a non-crossing path
of length $m$, -- a contradiction. $\Box$

%\noindent {\bf Algorithm.} Based on the ideas of
%the proof of Theorem~\ref{1.2}, we can design an algorithm
%to find a non-crossing 
%monochromatic path of length $m=\lfloor n^{2/3}/3\rfloor$ in a
%complete $2$-colored geometric graph on $n$ vertices in time $O(n^2)$,
%as follows.

%\begin{itemize}

%\item[1.] Consider the vertices of $G$ from left to right,
%and for each of them find the number $b(v)$
%(defined in the proof of Theorem~\ref{1.2}),
%using the relation $b(v)=1+\max b(v')$, where the maximum is
%taken over all vertices $v'$ to the left of $v$
%with the edge $vv'$
%colored blue. Similarly, find the numbers $r(v)$.
%If any $b(v)$ or $r(v)$ is at least $m=cn^{2/3}$ for an appropriately large
%constant $c$, then return the corresponding path.
%[This takes $O(n^2)$ time.]

%\item[2.] Find all entries of the matrix
%$M=(m_{b,r}:b,r\in\{0,1,\dots,m-1\})$ defined by
%$$m_{b,r}=\left\{ {{0,\ \ \ {\rm if}\ (b,r)\not\in\u,}
%     \atop{1,\ \ \ {\rm if}\ (b,r)\in\u.}}\right.$$
%Using this matrix, find the numbers
%$\q+-(b,r),b,r\in\{0,1,\dots,m-1\}$,
%(defined in the proof of Theorem~\ref{1.2}) as follows.
%For $b=m$ and for any $r$, set $\q+-(m,r)=0$.
%Similarly, for $r=0$ and for any $b$, set $\q+-(b,0)=0$.
%For other entries $\q+-(b,r)$, proceed by induction on $r-b$.
%Once we have found $\q+-(b+1,r-1)$, $\q+-(b+1,r)$, and $\q+-(b,r-1)$,
%we can set
%$$\q+-(b,r):=\q+-(b+1,r)+\q+-(b,r-1)
%-\q+-(b+1,r-1)+m_{b,r}.$$

%Analogously find the numbers $\q-+(b,r)$.
%[$O(n^2)$ time.]

%\item[3.] Find $1\le b, r\le m-1$ such that
%$$|\q+-(b, r)|\ge m+1,\ \ \ \ \ |\q-+(b, r)|\ge m+1.$$
%Following the proof of Theorem~\ref{1.2},
%find two $\lceil(m+1)/2\rceil$-element
%sets separated by a vertical line, such that
%all edges between them have the same color.
%In this situation, it is known [HS92] how to find a monochromatic
%non-crossing path passing through all
%points of these subsets, in time $O(m\log m)= O(n\log n)$.

%\end{itemize}

In Theorem~\ref{1.2}, the edges of a complete geometric graph $G$ are
colored by two colors. If they are colored by $r\ge2$ colors,
we obtain the following.

\begin{theorem}\label{r}
Every complete geometric graph of $n$ vertices whose edges are colored
by $r\ge 2$ colors, contains a non-crossing path of length
$\Omega(n^{2/(2r-1)})$, all of whose edges are of the same color.
\end{theorem}

\noindent {\bf Proof.} Let the edges of $G$
be colored by $1,2,\dots,r$. Suppose that
$G$ contains no non-crossing path of length $m$.
For each color $i$, define
a function $f_i$ on the vertex set of $G$ such that $f_i(v)$
is the length of the longest $x$-monotone monochromatic path
of color $i$, whose rightmost
point is $v$. Thus, for any
vertex $v$, we have an $r$-tuple $f(v)=(f_1(v),\dots,f_r(v))$
of integers between $0$ and $m-1$. Of course, $f(v)\ne f(v')$
for $v\ne v'$, since $f(v)$ and $f(v')$ differ
in the $i$-th coordinate, where $i$ is the color of the edge $vv'$.
We now show by induction on $r$ that the number of vertices of $G$ is
at most $O(m^{r-1/2})$. For $r=2$, this was shown in the proof of
Theorem~\ref{1.2}. Suppose now that $r>2$ and that the statement
holds for $r-1$. Define
$\u$ as the set of all $r$-tuples $f(v)$, where $v$ is a vertex of $G$.
The set $\u$ is a disjoint union of $m$ sets $\u_j,j=0,1,\dots,m-1$,
where $\u_j$ consists of the $r$-tuples of $\u$ whose last
coordinate is $j$. For each $j$, all edges between the vertices
corresponding to elements of $\u_j$ are colored by colors
$1,2,\dots,r-1$. By the inductive assumption, the size of $\u_j$
is at most $O(m^{r-3/2})$. Consequently, the size of $\u$
is at most $O(m^{r-1/2})$, and the result follows. $\Box$

\section{Paths in convex geometric graphs -- Proof of Theorems~\ref{1.3} and
\ref{1.4}}

The proof of Theorem~\ref{1.3} is based on a result of Perles
(Theorem~\ref{1.4}), whose proof is as follows.

\noindent {\bf Proof of Theorem~\ref{1.4}.}
Let $G$ be a convex geometric graph with vertices $u_1,u_2,\ldots,
u_n$ in clockwise order and with $|E(G)|=m> \lfloor (k-1)n/2 \rfloor$.
For convenience, let $u_0=u_n$ and $u_{n+i}=u_i$.

Fix $E_0=\emptyset$, and define $E_1,E_2,\ldots,E_m$ inductively, as follows.
There exists an edge $e_i\in \overline{E}_{i-1}=E(G)\setminus E_{i-1}$
such that one of the closed halfplanes determined by $e_i$ does not fully
contain any element of
$E(G)\setminus (E_{i-1}\cup \{e_i\})$.
Such an edge will be called an {\em extreme} edge
with respect to $\overline{E}_{i-1}$. Let $E_{i}=E_{i-1}\cup\{e_i\}$.

We also define some nonnegative integers $c_i(u_j)$ and $d_i(u_j)$.
For any vertex $u_j$, let $I=I(u_j)$ be the smallest integer
such that $E_I$ contains all edges of $G$ incident to $u_j$.
Suppose first that $i<I$. Then, starting at $u_j$
and visiting the vertices of the $G$
in clockwise order, let $u_p$ and $u_q$ be the first and the last
vertex such that $u_ju_p, u_ju_q\in \overline{E}_i$.
Let $c_i(u_j)$ (resp.
$d_i(u_j)$) denote the length of the longest non-crossing path in
$E_i$ starting at $u_j$, all of whose vertices are in
$\{ u_j, u_{j+1}, \ldots, u_{p-1}\}$
(resp. $\{ u_{q+1},u_{q+2},\ldots, u_j\}$).
Next, if $i=I$, then $e_i=u_ju_p$ for some vertex $u_p$.
Since $e_i$ is an extremal edge with respect to $\overline{E}_{i-1}$, we may
suppose,
by symmetry, that $\overline{E}_i$ has no element on the vertex set
$\{ u_j, u_{j+1},\ldots, u_{p-1},u_p\}$. If this is the case, then let
$c_i(u_j)$ (resp.
$d_i(u_j)$) denote the length of the longest non-crossing path in
$E_i$ starting at $u_j$, all of whose vertices lie in
$\{ u_j, u_{j+1}, \ldots, u_p\}$
(resp. $\{ u_{p+1},u_{p+2},\ldots, u_j\}$). (Otherwise we
change the orientation.)
Finally, if $i>I$ then put $c_i(u_j)=c_I(u_j)$ and $d_i(u_j)=d_I(u_j)$.

\begin{claim}
For every $0\le i\le m$,
$$\sum_{j=1}^nc_i(u_j) +\sum_{j=1}^nd_i(u_j)\ge 2|E_i|.$$
\end{claim}

The claim is clearly true for $i=0$. Let $0<i\le m$,
and assume that the assertion has already been proved for $i-1$.
Suppose that the endpoints of ${e_i}$ are $u_j$ and $u_l$.
Since $c_i(u)\ge c_{i-1}(u)$ and $d_i(u)\ge d_{i-1}(u)$ for every fixed
vertex $u$, it is enough to prove that
$$c_i(u_j)+d_i(u_j)+c_i(u_l)+d_i(u_l)
\ge c_{i-1}(u_j)+d_{i-1}(u_j)+c_{i-1}(u_l)+d_{i-1}(u_l)+2.$$

However,  we have either $c_i(u_j)>d_{i-1}(u_l)$ and
$d_i(u_l)>c_{i-1}(u_j)$ or $c_i(u_l)>d_{i-1}(u_j)$ and $d_i(u_j)>c_{i-1}(u_l)$,
depending on which side of $e_i=u_ju_l$ contains no edge of
$\overline{E}_i$, and the statement follows.
\medskip

Now it is easy to complete the proof of Theorem~\ref{1.4}.
Since $|E_m|>\lfloor (k-1)n/2\rfloor$, there is $1\le j\le n$
for with $c_m(u_j)+d_m(u_j)\ge k$. By the definition of $c_m$ and $d_m$,
this means that there is a non-crossing path of length $k$,
passing through $u_j$.
 
The following construction shows that the bound in Theorem~\ref{1.4} is tight.

\noindent {\bf Construction.}  
Let $0,1,\ldots,n-1 \ \ ({\mbox {mod}}\  n)$ denote the vertices of a
regular $n$-gon.
\begin{itemize}
\item[(i)] If $n \equiv k \ \ ({\mbox {mod}}\  2)$,
then connect each vertex to the $k-1$ vertices furthest from it.

\item[(ii)] If $n \not\equiv k \ \ ({\mbox {mod}}\  2)$,
then connect each vertex $i$ to the $k-2$ vertices furthest from $i$, and
for $0\le i\le \lfloor {n\over 2} \rfloor -1$, also to 
$i+{n-k-1\over 2}$.
\end{itemize}

In case (i), every edge has at least ${n-k\over 2}$ vertices on 
both sides. In particular, this holds for the first and last edges of any 
non-crossing path. This implies that any such path misses at least $n-k$ 
vertices, so it is of length at most $k-1$.

In case (ii), suppose that $k+3\le n$.
Consider any non-crossing path $P$. Call an edge of $P$ extremal
if the whole path $P$ lies in one of the closed halfspaces determined by
$P$. If $P$ has at least three extremal edges, then it has at most
$n-3({n-k-1\over 2})\le k$ vertices, showing that its length is at most
$k-1$. However, if $P$ has only two extremal edges, then 
$P$ is a ``zigzag'', in particular, for each $j$, 
$\lfloor {n\over 2}\rfloor \ge j\ge {n-k+1\over 2}$ it has at most two edges
of the form $(i,i+j)$. If at most one edge of $P$ is of the form
$(i,i+{n-k+1\over 2})$, then $P$ contains at most $k-1$ edges.
Otherwise, the first and the last edges of $P$ are of the form
$(i,i+{n-k+1\over 2})$ and $(j,j+{n-k+1\over 2})$ with
$0\le i< i+ {n-k+1\over 2}<j\le\lfloor {n\over 2}\rfloor-1$.
In this case, the length of $P$ is at most
$$2\Bigl( j-\Bigl( i+{n-k+1\over 2}\Bigr) +1\Bigr )\le
2\Bigl( \Bigl\lfloor {n\over 2}\Bigr\rfloor - {n-k+1\over 2}\Bigr) \le k-1\ ,$$
as reqired.

The case $n=k+1$ can be treated similarly. 
$\Box$

We prove the following equivalent form of Theorem~\ref{1.3}.

\begin{theorem}\label{4}
Let ${\cal P}_k$ be the class of all
non-crossing paths of length $k$.
Then $R_c({\cal P}_k)= 2k-1$ unless $k=1$.
\end{theorem}

\noindent {\bf Proof.} First, we show that $R_c({\cal P}_k)> 2k-2$.
Let $G$ be a convex geometric graph on $2k-2$ vertices, and let
$p, v_1, v_2, \ldots, v_{k-2}, q, u_1$, $u_2, \ldots, u_{k-2}$
be its vertices listed in clockwise order. For all $i, j$,
color all edges $(v_i, v_j)$, $(p, v_i)$, and $(q, v_i)$ blue;
$(u_i, u_j)$, $(p, u_i)$, and $(q, u_i)$ red;
$(v_i, u_j)$ red if $i+j$ is odd and blue if $i+j$ is even.
The edge $(p, q)$ can have any color.
It is not difficult to check that this graph contains
no non-crossing monochromatic path of length $k$.

%figure will be here

For the upper bound, first let $k$ be even and take a convex complete
geometric graph on $2k-1$ vertices, all of whose edges are colored
red or blue. This graph has $(2k-1)(k-1)$ edges, so one of the color
classes (say, red) contains at least
$\lceil (2k-1)(k-1)/2\rceil>\lfloor (2k-1)(k-1)/2\rfloor$ edges.
Therefore, by Theorem \ref{1.4}, there is a non-crossing red path of length
$k$.

If $k$ is odd, then we have to be more careful. Suppose
there is a 2-coloring of the edges of a complete geometric graph $G$
on $2k-1$ vertices without a non-crossing
path of length $k$. It follows from Theorem~\ref{1.4} that $(2k-1)(k-1)/2$
edges are red and the same number of edges are blue. Let $G_b$
denote the subgraph of $G$ obtained from $G$ by removing all red edges.
Analyzing the proof of Theorem~\ref{1.4} for $G_b$, we obtain that
(in the notation of the proof of Theorem~\ref{1.4})
$$\sum_{j=1}^nc_i(u_j) +\sum_{j=1}^nd_i(u_j)= 2|E_i|,\ \ \ \ \
i=1,2,\dots,m.$$
Consequently,
$$c_i(u_j)+d_i(u_j)+c_i(u_l)+d_i(u_l)
=c_{i-1}(u_j)+d_{i-1}(u_j)+c_{i-1}(u_l)+d_{i-1}(u_l)+2.$$

\noindent (Otherwise, we would have $c_m(u_j)+d_m(u_j)\ge k$ for some $j$, and
we could find a non-crossing path of length $k$.)
This means, for example, that if $e_i=u_ju_l$
and $\overline{E}_i$ has no element on the vertex set
$\{ u_j, u_{j+1},\ldots, u_{l-1},u_l\}$,
then $c_i(u_j)=d_{i-1}(u_l)+1$,
$d_i(u_l)=c_{i-1}(u_j)+1$.

Looking at all possible ways how we may arrange the edges
of $G_b$ in the sequence $e_1,e_2,\dots, e_m$, we obtain
the following proposition.

\begin{proposition}\label{pr}
Let $v,w\in\{1,2,\dots 2k-1\}$.
\begin{itemize}
\item[{\rm (a)}] If $u_vu_w$ is blue, then
at least one of the longest blue non-crossing paths starting at $u_v$,
all of whose vertices lie in $\{u_v,u_{v+1},\dots,u_w\}$,
contains the edge $u_vu_w$.

\item[{\rm (b)}] If $u_vu_w$ is blue, then at least
one of the longest blue non-crossing paths starting at $u_w$,
all of whose vertices lie in $\{u_v,u_{v+1},\dots,u_w\}$,
contains the edge $u_vu_w$.

\item[{\rm (c)}] If $u_vu_w$ is red, then
at least one of the longest blue non-crossing paths starting at $u_v$,
all of whose vertices lie in $\{u_v,u_{v+1},\dots,u_w\}$,
does not contain $u_w$.

\item[{\rm (d)}] If $u_vu_w$ is red, then
at least one of the longest blue non-crossing paths starting at $u_w$,
all of whose vertices lie in $\{u_v,u_{v+1},\dots,u_w\}$,
does not contain $u_v$.
\end{itemize}
\end{proposition}

Exchanging the roles of the colors, one can formulate a similar statement about
red
paths in the graph $G_r$ obtained from $G$ by deleting all blue edges.

Consider the $2k-1$ edges $u_iu_{i+1}$. At least $k$ of them
are colored by the same color (blue, say). Let
$u_pu_{p+1}\dots u_{q}$ be the longest non-crossing blue path
using some of the
edges $u_iu_{i+1}$ (certainly, its length is at least 2).
First, observe that Proposition~\ref{pr} (c) yields
that all edges within $\{u_p,u_{p+1},\dots,u_{q}\}$
are blue. Indeed, if $u_su_t,p\le s< t\le q$, was a red edge
such that all other edges $u_{s'}u_{t'},s\le s'<t'\le t$ were blue,
then Proposition~\ref{pr} (c) would be false with $u=s$ and $w=t$.
This implies that the blue path $u_pu_{p+1}\dots u_{q}$ cannot visit
all or all but one of the vertices of $G$.
By the maximality of this path, the edges
$u_{p-1}u_p$ and $u_qu_{q+1}$ are red. It follows from the
the dual of Proposition~\ref{pr} (a) and (c) with $v=p-1$ and $w=q+1$ that
$u_pu_{q+1}$
is blue. Analogously, $u_{p-1}u_q$ is also blue.

Suppose now that some of the edges $u_{p-1}u_r, r=p+1,p+2,\dots, q-1$,
are red. Take one of them for which $r$ is maximum. Then
Proposition~\ref{pr} (b) would be violated for $v=p-1$ and
$w=r+1$. Thus, all edges $u_{p-1}u_r, r=p+1,p+2,\dots, q$,
are blue. Analogously, all edges $u_{q+1}u_r, r=p,p+1,\dots, q-1$,
are also blue.

The edge $u_{p-2}u_{p-1}$ cannot be red. Otherwise, starting with the longest
non-crossing red path
$u_pu_{p-1}\dots$ and using a similar argument as above, we would conclude that
$u_{p-1}u_{p+1}$ must be red, but we already know that it is blue.
Thus, $u_{p-2}u_{p-1}$ is blue, and we get a contradiction with
Proposition~\ref{pr}
(a) or (c) for $v=p-2$ and $w=p+1$.
$\Box$

%The idea of the proof of Theorem \ref{1.4} can be adopted to derive a more
%general result due to Perles [MP93, p. 292]. A tree is called a caterpillar
%if it does not contain three edge-disjoint paths of length 2 starting at the
%same vertex.


%\begin{theorem}\label{5}
%Let $H$ be a caterpillar with $k$ edges.
%If a convex geometric graph of $n$ vertices has more than
%$\lfloor (k-1)n/2 \rfloor$ edges than it contains a non-crossing
%subgraph isomorphic to $H$.
%\end{theorem}

%\smallskip

%\noindent {\bf Algorithm.} Suppose $G$ is a convex geometric graph with
%$n\ge k+1$ vertices $u_1, u_2, \ldots, u_n$, $n\ge k+1$, and $G$ has
%more than $\lfloor(k-1)n/2\rfloor$ edges. By Theorem~\ref{1.4}, $G$
%contains a non-crossing path of length $k$. It can be found in $O(n^2)$
%time, or, if $G$ has  $O(nk)$ edges, then also in
%$O(nk\log n)$ time, as follows.
%Let the {\em length}
%of an  edge $u_iu_j$ be defined as min($|i-j|, n-|i-j|$) for  $1\le i,
%j\le n$.
%So every edge has length at most $n/2$. We use the notation of the proof.

%\begin{itemize}

%\item[1.] List the edges of $G$ in increasing order of length,
%$e_1, e_2,\ldots, e_m$. (The order of the edges of the same length is
%arbitrary.)
%This can be done in two different ways:

%\noindent (i) For the {\em complete} graph on the same vertex set,
%such a list is instantly available. Go over this list and
%delete all edges missing from $G$.
%[This can be done  in $O(n^2)$ time.]

%\noindent (ii) Order the edges of $G$ according to their lengths.
%[This can be done in $O(nk\log n)$ time, provided that $G$ has $O(nk)$ edges.]

%\item[2.] At start, $E_0=\emptyset$, $c_0(u_j)=d_0(u_j)=0$, $1\le j\le n$.
%For $1\le i\le m$, at the $i$-th step we have
%$E_{i-1}=\{e_1, e_2,\ldots, e_{i-1}\}$,
%$c_{i-1}(u_j)$, and $d_{i-1}(u_j)$,
%and we also have the corresponding paths of length
%$c_{i-1}(u_j)$ and $d_{i-1}(u_j)$, respectively, ending at $u_j$, for each
%$1\le j\le n$. Observe that $e_i$ is an extreme edge with respect to
%$\overline{E}_{i-1}$. So let $E_i=E_{i-1}\cup e_i$. Update $c(u), d(u)$, and
%the list
%of corresponding paths at the endpoints of $e_i$.
%Do the $(i+1)$-st step.
%[Steps 1 through $m$ can be done in a total of $O(nk)$ time.]

%\item[3.] It follows from Theorem~\ref{1.4} that after the $m$-th step
%there will be a vertex $u$ with $c(u)+d(u)\ge k$. Return the union of the
%corresponding paths of lengths  $c(u)$ and $d(u)$. [$O(n)$ time.]

%\end{itemize}

%To find a monochromatic non-crossing path of length
%$\lfloor n/2\rfloor$ (ensured by Theorem~\ref{1.3})
% in a complete 2-colored graph,
% we first apply the above algorithm
%on the graphs $G_b$ and $G_r$ containing all blue and all
%red edges of $G$, respectively. If we don't find
%a monochromatic non-crossing path of length $\lfloor n/2\rfloor$, then we use
% the proof of Theorem~\ref{4} to improve the performance of the algorithm
%(to increase at least one of the values $c(v)$, $d(v)$)
%so that it will find the desired path in time $O(n^2)$.



\section{General estimates -- Proof of Theorem~\ref{1.5}}

For any set of $n$ points $P$ in the plane, an $i$-element subset
of $P$ is called an $i$-{\em set} if it can be
obtained by intersecting $P$ with an open half-plane.
It is easy to see
that all $i$-sets can be generated by the following procedure [ELSS73]:
Take an oriented line $\ell$ passing through precisely one point $p \in P$
and having $i$ elements of $P$ on its left side. Rotate $\ell$ around $p$
in the clockwise direction until it hits another point $q \in P$, and then
continue the rotation around $q$, etc. Whenever $\ell$ passes through only
one element of $P$, the points lying on its left side form an $i$-set.

Any geometric subgraph $K_{R({\cal G})}$ induced by an $R({\cal G})$-element
subset
of $P$ contains a subgraph of the class ${\cal G}$, all of whose edges
are of the same color.
If these edges are red (blue), we say that the {\em type} of the
corresponding subset is {\em red (blue)}.
Note that a set may have both types.


\begin{lemma}\label{L1}
Let ${\cal G}$ be any class of geometric graphs.
Then $R(2{\cal G})\le 2R({\cal G})+1.$

\end{lemma}

Let $N=2R({\cal G})+1$ and let $P$ be the vertex set of a complete
geometric graph $K_N$ whose edges are colored by red and blue.

If all $R({\cal G})$-sets of $P$ have the same type, then take two disjoint
$R({\cal G})$-sets. Both contain a monochromatic geometric
subgraph belonging to ${\cal G}$, so their union is a
monochromatic member of $2{\cal G}$.

On the other hand, if there are two $R({\cal G})$-sets of different types,
then we can also find two $R({\cal G})$-sets, $A$ and $B$, of different types
such that $|A\cup B|=R({\cal G})+1$
and that $P\setminus(A\cup B)$ is also an
$R({\cal G})$-set. The type of $P\setminus(A\cup B)$
 will coincide with the type of $A$ or $B$.
$\Box$

\medskip

\noindent {\bf Proof of Theorem \ref{1.5}.}
Part (i) is an immediate corollary of Lemma~\ref{L1}.

Let ${\cal G}$ be a (fixed) class of geometric graphs.
Let $r=r(k, l)$ be the the smallest number with the property that
every complete geometric graph with $r$ vertices, whose edges are colored by
red and blue, contains either a subgraph belonging to $k{\cal G}$,
all of whose edges are red, or a subgraph belonging to $l{\cal G}$,
all of whose edges are blue. So, $R=R({\cal G})=r(1, 1)$,
$R(k{\cal G})=r(k, k)$.

\begin{lemma}\label{L2}
For $k\ge l\ge 1$
$$r(k, l)=r(l, k)\le (R+1)k+\left\lceil {R+1\over 2}\right\rceil l-\left\lceil {R+1\over 2}\right\rceil .$$
\end{lemma}

\noindent {\bf Proof.} By simmetry, clearly $r(k, l)=r(l, k)$. 
We proceed by induction on $k$ and $l$.
First we show that $r(k, 1)\le kR$. Let $G$ be 
a complete geometric graph with $kR$ vertices, whose edges are colored by
red and blue. Suppose that no two vertices determine a vertical 
line. Then we can choose $k-1$ vertical lines that divide the vertex set of 
$G$ into $k$ equal parts. Since each part contains $R$ of the vertices,
the subgraph spanned by every part contains a monochromatic copy of 
a geometric graph from the class ${\cal G}$. Either all of them are 
red or one of them is blue. Therefore, the lemma holds for
any pair $(k, l)$, where either $k=1$ or $l=1$. 

Let $k\ge l$ be fixed, and suppose that we already know that the Lemma is true
for every pair $(k', l')\ne (k, l)$, where $k'\ge k, l'\ge l$.
 
Consider a complete geometric graph $G$ with vertex set $V$, 
whose edges are colored by red and blue and 
$$|V|=(R+1)k+\left\lceil {R+1\over 2}\right\rceil l-\left\lceil {R+1\over 2}\right\rceil .$$

By Theorem~\ref{1.5} (i), for any $n\ge 1$, if  $f(n)=2^n(R+1)-1\le |V|$,
then any geometric subgraph induced by an $f(n)$-set contains a monochromatic
subgraph from the class $2^n{\cal G}$. Its color will be the {\em type}
of the corresponding $f(n)$-set.

If there are two $f(n)$-sets of different types, we can cut off an $(f(n)+1)$-set
which contains an $f(n)$-set of both types. Since 
$$(R+1)k+\left\lceil {R+1\over 2}\right\rceil l-2^n(R+1)\ge  
(R+1)(k-2^n)+\left\lceil {R+1\over 2}\right\rceil (l-2^n),$$
\noindent we can apply the induction 
hypothesis for the subgraph induced by the rest of the vertices, with
$k'=k-2^n, l'=l-2^n$. 

So we can assume that for all $n$, all $f(n)$-sets are of the same type, provided $f(n)=2^n(R+1)-1\le |V|$.
Suppose that for $n_1<n_2$, the $f(n_1)$ and $f(n_2)$-sets are of different types.
Then, there exists an $n_1\le n<n_2$ such that the $f(n)$ and $f(n+1)$-sets are also of different types.
Cut off an $f(n+1)$-set. Since it contains an $f(n)$-set, the subgraph induced by 
the $f(n+1)$-set contains a blue (resp. red) subgraph from the class $2^{n+1}{\cal G}$
and a red (resp. blue) subgraph from the class $2^n{\cal G}$. 

If the $f(n+1)$-sets are of type blue, then either $l\le 2^{n+1}$ and we are done, or we can apply the induction hypothesis
for the graph induced by the remaining vertices with $k'=k-2^n$ and $l'=l-2^{n+1}$
since it is easy to check that
$$(R+1)k+\left\lceil {R+1\over 2}\right\rceil l-2^{n+1}(R+1) \ge  
(R+1)(k-2^n)+\left\lceil {R+1\over 2}\right\rceil (l-2^{n+1}).$$

On the other hand, if the $f(n+1)$-sets are of type red then we can assume 
that $k>2^{n+1}$ and $l>2^n$ and we can 
apply the induction hypothesis with $k'=k-2^{n+1}$ and $l'=l-2^{n}$
since 
$$(R+1)k+\left\lceil {R+1\over 2}\right\rceil l-2^{n+1}(R+1)\ge  
(R+1)(k-2^{n+1})+\left\lceil {R+1\over 2}\right\rceil (l-2^n)$$
\noindent and
$$(R+1)k+\left\lceil {R+1\over 2}\right\rceil l-2^{n+1}(R+1)\ge
(R+1)(l-2^n)+\left\lceil {R+1\over 2}\right\rceil (k-2^{n+1}).$$

Therefore, in the sequel we assume that for {\em all} $n$, all 
$f(n)$-sets are of the same type. For simplicity we assume that 
they are of type {\em red}. The case where these sets are of type {\em blue}
can be settled very similarly.
Write $k$ in base 2, that is, $k=2^{n_1}+2^{n_2}+\ldots +2^{n_a}$, $n_1<n_2<\ldots <n_a$.
Let $V_0=V$. By the assumption, every $f(n_1)$- and $f(n_2)$-set of $V_0$ are of type red.
Let $S_1$ be an $f(n_1)$-set and let $V_1=V_0\setminus S_1$. If every $f(n_2)$- and $f(n_3)$-set 
of $V_1$ are of type red, then let $S_2$ be such an $f(n_2)$-set and let $V_2=V_1\setminus S_2$.
In general, if $V_i$ has already been defined by this procedure and every $f(n_{i+1})$- and $f(n_{i+2})$-set 
of $V_i$ are of type red, then let $S_{i+1}$ be any $f(n_{i+1})$-set and let $V_{i+1}=V_i\setminus S_{i+1}$.
Otherwise, if not all $f(n_{i+1})$-sets or not all $f(n_{i+2})$-sets of $V_i$ 
are of type red, or $i=a-1$,
then stop and let $j=i$.

If $j=a-1$, then $V_{a-1}$ still has an $f(n_a)$-set, $S_a$ of type red,
and $S_1\cup S_2\cup \ldots \cup S_a$ contains a red subgraph from the class $k{\cal G}$ and we are done.
Suppose $j<a-1$. We distinguish two cases.

\noindent {\bf a.} {\em There is an $f(n_{j+1})$-set of $V_j$ of type blue.} 
\noindent Since all $f(n_{j+1})$-sets of 
$V_{j-1}$ were of type red, at least one of the  $f(n_{j+1})$-sets of 
$V_j$ is of type red. Therefore, we can find an $(f(n_{j+1})+1)$-set, $S_{j+1}$, 
which contains an $f(n_{j+1})$-set of both types. $|S_1\cup S_2\cup \ldots \cup S_{j+1}|\le (2^{n_1}+2^{n_2}+\ldots +2^{n_{j+1}})(R+1)$
and $S_1\cup S_2\cup \ldots \cup S_{j+1}$ contains a red subgraph from the class 
$(2^{n_1}+2^{n_2}+\ldots +2^{n_{j+1}}){\cal G}$ and a blue subgraph from the class $2^{n_{j+1}}{\cal G}$. 
If either $k\le 2^{n_1}+2^{n_2}+\ldots +2^{n_{j+1}}$ or $l\le 2^{n_{j+1}}$
then we are done. Otherwise, 
easy calculation shows that we can apply the induction hypothesis for 
for the graph induced by the remaining vertices with $k'=k-(2^{n_1}+2^{n_2}+\ldots +2^{n_{j+1}})$ and $l'=l-2^{n_{j+1}}$.

\noindent {\bf b.} {\em Every $f(n_{j+1})$-set of $V_i$ are of type red, but there is an $f(n_{j+2})$-set of $V_j$ of type blue.}
\noindent In this case, there exists an $n_{j+1}\le n<n_{j+2}$ such that  
every $f(n)$-set of $V_i$ are of type red, but there is an $f(n+1)$-set of $V_j$ of type blue.
Then let $S_{j+1}$ be an $f(n+1)$-set of $V_j$ of type blue. Clearly, it contains 
an $f(n)$-set of $V_j$, which is of type red.
$|S_1\cup S_2\cup \ldots \cup S_{j+1}|\le (2^{n_1}+2^{n_2}+\ldots +2^{n_j}+2^{n+1})(R+1)$
and $S_1\cup S_2\cup \ldots \cup S_{j+1}$ contains a red subgraph from the class 
$(2^{n_1}+2^{n_2}+\ldots +2^{n_j}+2^n){\cal G}$ and a blue subgraph from the class $2^{n+1}{\cal G}$. 
Again, easy calculation shows that we can proceed as in case a.
$\Box$

Return to the proof of Theorem~\ref{1.5}. Part (ii) is an immediate 
corollary of Lemma 5.2.  In part (iii),
if all $R_c({\cal G})$-sets have the same type then, using the convexity
of the geometric graph, we can take $k$  disjoint
$R_c({\cal G})$-sets and we get a monochromatic
geometric graph from $k{\cal G}$.

If there are two $R({\cal G})$-sets of different types,
we can proceed by induction as in part (ii). $\Box$

%\smallskip

%\noindent {\bf Algorithms.} Following the approach of [KPTT97],
%where $G$ was just an edge, one can obtain an  $O(n^{\log\log n+2})$
%time algorithm to find a monochromatic subgraph belonging to
%$k{\cal G}$ in a complete 2-colored geometric graph of
%$n=(R({\cal G})+1)k - 1$ vertices, provided that $k$ is a power of 2.
%The same approach yields an $O(n^{\log\log n+2})$ time algorithm
%to find a monochromatic subgraph belonging to $k{\cal G}$ in a complete
%2-colored geometric graph of
%$n=\lfloor 3R({\cal G})/2\rfloor k - \lfloor R({\cal G})/2\rfloor$
%vertices (see Theorem~\ref{1.5} (i) and (ii)).

%However, it is much easier to find a monochromatic subgraph belonging to
%$k{\cal G}$ in a complete
%2-colored {\em convex} geometric graph of $n=(R_c({\cal G})+1)k-1$ vertices
%(see Theorem\ref{1.5} (iii)). This can be done in $O(n^2)$ time as follows.

%\smallskip

%Let $r=R_c({\cal G})$ for simplicity. Let $v_1, v_2, \ldots, v_r$
%be the vertices of a 2-colored complete convex geometric graph,
%listed in clockwise order.
%The algorithm will be described recursively. Its running time
%is denoted by $f(n)$.

%\begin{itemize}

%\item[1.] Find a monochromatic copy of $G$ in the subgraphs
%induced by $\{v_{ir+1}, v_{ir+2},\ldots, v_{(i+1)r}\}$, for
%$i=0, 1,\ldots, n-1$. [This can be done in $O(n)$ time.]

%\item[2.] If all of these monochromatic copies have the same color,
%then return their union. If not, then find two consecutive ones, say,
%in $\{v_1, v_2,\ldots, v_r\}$ and
%$\{v_{r+1}, v_{r+2},\ldots, v_{2r}\}$, that have different colors.
%[$O(n)$ time.]

%\item[3.] Each of the subgraphs
%spanned by $\{v_{j+1}, v_{j+2},\ldots, v_{j+r}\}$
%contains a monochromatic copy of $G$, for
%$j=0, 1,\ldots, r$. Find two consecutive ones, say in $\{v_1, v_2,\ldots,
%v_r\}$
%and $\{v_2, v_3,\ldots, v_{r+1}\}$, which have different different colors.
%[$O(1)$ time.]

%\item[4.] Call the algorithm recursively for the  subgraph
%induced by $\{v_{r+2}, v_{r+3},\ldots, v_n\}$, to find a
%mono\-chromatic subgraph which belongs to
%$(k-1){\cal G}$. Depending on its color, augment it with the mono\-chromatic copy
%of $G$ contained in $\{v_1, v_2,\ldots, v_r\}$ or
%$\{v_{r+1}, v_{r+2},\ldots, v_{2r}\}$. \newline  [$f(n-r)$ time.]

%\end{itemize}

%Thus, the running time $f(n)$ of this algorithm satisfies the inequality
%$f(n)\le f(n-r)+O(n)$, which implies that $f(n)=O(n^2)$.


\section{Triangles -- Proof of Theorem~\ref{1.6}}

The proof is quite technical, therefore we sketch here only the main ideas.

It is sufficient to show 
that $R_{\Delta}(k)>7k-7$ for every $k$.
Indeed, if $R_{\Delta}(k)\le 7k-2$ for some positive integer $k$,
an application of Theorem \ref{1.5} with $k=8$ and ${\cal G}=k{\cal T}$
would yield $R_{\Delta}(8k)\le 7(8k)-9$, a contradiction.

\noindent {\bf Construction.} Let $k$ be a positive integer, $n=7k-7$.
Let $0, 1,\ldots, 7k-8$ denote the vertices of a regular $n$-gon,
in clockwise order. If two vertices are separated by $m-1$ others, then we
say that the {\em length} of the edge connecting them is
$m$ ($m\le \lfloor n/2\rfloor $). A vertex is colored red if
$i\equiv$ 0, 1, 3, or 5 (mod 7),
and blue otherwise.

We color the edges $ij$ ($0\le i\ne j\le n-1$)
according to the following rules.
Let $\lambda$ denote the length of $ij$.
\begin{itemize}
\item[(a)] If $\lambda \equiv 1, 4,\ {\mbox {or}}\  6 \ \ ({\mbox {mod}}\  7)$,
let $ij$ be blue.

\item[(b)] If $\lambda \equiv 2\  {\mbox {or}}\  3 \ \ ({\mbox {mod}}\  7)$,
let $ij$ be red.

\item[(c)] If $\lambda \equiv 5 \ \ ({\mbox {mod}}\  7)$, let $ij$ be colored
with the color of its starting point in the clockwise direction.

\item[(d)] If $\lambda \equiv 0 \ \ ({\mbox {mod}}\  7)$, let $ij$ be
colored with the color other than the color of $i+1 \ \ ({\mbox {mod}}\  7)$.

\end{itemize}

%The proof of the fact that this complete
%geometric graph contains no $k$ disjoint triangles of the
%same color is quite technical, so it is omitted in this abstract.
%This implies that $R_{\Delta}(k)>7k-7$, as required. $\Box$




$$
\setlength{\unitlength}{19mm}
\begin{picture}(3, 3)
\linethickness{0.6pt}
\small


% BLUE
\put(3, 1.65){
\begin{picture}(3, 3)

\put(\nx, \ny){\circle*{0.07}} \put(1.05, 0.2224){$13$}
\put(\mx, \my){\circle{0.07}}  \put(0.8, 0.7){$12$}
\put(\lx, \ly){\circle*{0.07}} \put(0.47, 0.95){$11$}
\put(\kx, \ky){\circle{0.07}}  \put(-0.1, 1.1){$10$}
\put(\jx, \jy){\circle*{0.07}} \put(-0.55, 0.95){$9$}
\put(\ix, \iy){\circle{0.07}}  \put(-0.91, 0.7){$8$}
\put(\hx, \hy){\circle{0.07}}  \put(-1.15, 0.2224){$7$} 
\put(\gx, \gy){\circle*{0.07}} \put(-1.15, -0.28){$6$} 
\put(\fx, \fy){\circle{0.07}}  \put(-0.96, -0.75){$5$}
\put(\ex, \ey){\circle*{0.07}} \put(-0.6, -1.05){$4$}
\put(\dx, \dy){\circle{0.07}}  \put(-0.03, -1.22){$3$}
\put(\cx, \cy){\circle*{0.07}} \put(0.5, -1.05){$2$}
\put(\bx, \by){\circle{0.07}}  \put(0.85, -0.75){$1$}
\put(\ax, \ay){\circle{0.07}}  \put(1.05, -0.28){$0$}

%1 hosszu
\el(\ax, \ay)(\bx, \by)
\el(\bx, \by)(\cx, \cy)
\el(\cx, \cy)(\dx, \dy)
\el(\dx, \dy)(\ex, \ey)
\el(\ex, \ey)(\fx, \fy)
\el(\fx, \fy)(\gx, \gy)
\el(\gx, \gy)(\hx, \hy)
\el(\hx, \hy)(\ix, \iy)
\el(\ix, \iy)(\jx, \jy)
\el(\jx, \jy)(\kx, \ky)
\el(\kx, \ky)(\lx, \ly)
\el(\lx, \ly)(\mx, \my)
\el(\mx, \my)(\nx, \ny)
\el(\nx, \ny)(\ax, \ay)

%4 hosszu
\el(\ax, \ay)(\ex, \ey)
\el(\bx, \by)(\fx, \fy)
\el(\cx, \cy)(\gx, \gy)
\el(\dx, \dy)(\hx, \hy)
\el(\ex, \ey)(\ix, \iy)
\el(\fx, \fy)(\jx, \jy)
\el(\gx, \gy)(\kx, \ky)
\el(\hx, \hy)(\lx, \ly)
\el(\ix, \iy)(\mx, \my)
\el(\jx, \jy)(\nx, \ny)
\el(\kx, \ky)(\ax, \ay)
\el(\lx, \ly)(\bx, \by)
\el(\mx, \my)(\cx, \cy)
\el(\nx, \ny)(\dx, \dy)

%6 hosszu
\el(\ax, \ay)(\gx, \gy)
\el(\bx, \by)(\hx, \hy)
\el(\cx, \cy)(\ix, \iy)
\el(\dx, \dy)(\jx, \jy)
\el(\ex, \ey)(\kx, \ky)
\el(\fx, \fy)(\lx, \ly)
\el(\gx, \gy)(\mx, \my)
\el(\hx, \hy)(\nx, \ny)
\el(\ix, \iy)(\ax, \ay)
\el(\jx, \jy)(\bx, \by)
\el(\kx, \ky)(\cx, \cy)
\el(\lx, \ly)(\dx, \dy)
\el(\mx, \my)(\ex, \ey)
\el(\nx, \ny)(\fx, \fy)

%5 hosszu
%\el(\ax, \ay)(\fx, \fy)
%\el(\bx, \by)(\gx, \gy)
\el(\cx, \cy)(\hx, \hy)
%\el(\dx, \dy)(\ix, \iy)
\el(\ex, \ey)(\jx, \jy)
%\el(\fx, \fy)(\kx, \ky)
\el(\gx, \gy)(\lx, \ly)
%\el(\hx, \hy)(\mx, \my)
%\el(\ix, \iy)(\nx, \ny)
\el(\jx, \jy)(\ax, \ay)
%\el(\kx, \ky)(\bx, \by)
\el(\lx, \ly)(\cx, \cy)
%\el(\mx, \my)(\dx, \dy)
\el(\nx, \ny)(\ex, \ey)

%7 hosszu
\el(\ax, \ay)(\hx, \hy)
%\el(\bx, \by)(\ix, \iy)
\el(\cx, \cy)(\jx, \jy)
%\el(\dx, \dy)(\kx, \ky)
\el(\ex, \ey)(\lx, \ly)
%\el(\fx, \fy)(\mx, \my)
\el(\gx, \gy)(\nx, \ny)


\put(-0.4, -1.6){Blue edges}
\end{picture}}

% RED
\put(0, 1.65){
\begin{picture}(3, 3)


\put(\nx, \ny){\circle*{0.07}} \put(1.05, 0.2224){$13$}
\put(\mx, \my){\circle{0.07}}  \put(0.8, 0.7){$12$}
\put(\lx, \ly){\circle*{0.07}} \put(0.47, 0.95){$11$}
\put(\kx, \ky){\circle{0.07}}  \put(-0.1, 1.1){$10$}
\put(\jx, \jy){\circle*{0.07}} \put(-0.55, 0.95){$9$}
\put(\ix, \iy){\circle{0.07}}  \put(-0.91, 0.7){$8$}
\put(\hx, \hy){\circle{0.07}}  \put(-1.15, 0.2224){$7$} 
\put(\gx, \gy){\circle*{0.07}} \put(-1.15, -0.28){$6$} 
\put(\fx, \fy){\circle{0.07}}  \put(-0.96, -0.75){$5$}
\put(\ex, \ey){\circle*{0.07}} \put(-0.6, -1.05){$4$}
\put(\dx, \dy){\circle{0.07}}  \put(-0.03, -1.22){$3$}
\put(\cx, \cy){\circle*{0.07}} \put(0.5, -1.05){$2$}
\put(\bx, \by){\circle{0.07}}  \put(0.85, -0.75){$1$}
\put(\ax, \ay){\circle{0.07}}  \put(1.05, -0.28){$0$}

%2 hosszu
\el(\ax, \ay)(\cx, \cy)
\el(\bx, \by)(\dx, \dy)
\el(\cx, \cy)(\ex, \ey)
\el(\dx, \dy)(\fx, \fy)
\el(\ex, \ey)(\gx, \gy)
\el(\fx, \fy)(\hx, \hy)
\el(\gx, \gy)(\ix, \iy)
\el(\hx, \hy)(\jx, \jy)
\el(\ix, \iy)(\kx, \ky)
\el(\jx, \jy)(\lx, \ly)
\el(\kx, \ky)(\mx, \my)
\el(\lx, \ly)(\nx, \ny)
\el(\mx, \my)(\ax, \ay)
\el(\nx, \ny)(\bx, \by)

%3 hosszu
\el(\ax, \ay)(\dx, \dy)
\el(\bx, \by)(\ex, \ey)
\el(\cx, \cy)(\fx, \fy)
\el(\dx, \dy)(\gx, \gy)
\el(\ex, \ey)(\hx, \hy)
\el(\fx, \fy)(\ix, \iy)
\el(\gx, \gy)(\jx, \jy)
\el(\hx, \hy)(\kx, \ky)
\el(\ix, \iy)(\lx, \ly)
\el(\jx, \jy)(\mx, \my)
\el(\kx, \ky)(\nx, \ny)
\el(\lx, \ly)(\ax, \ay)
\el(\mx, \my)(\bx, \by)
\el(\nx, \ny)(\cx, \cy)

%5 hosszu
\el(\ax, \ay)(\fx, \fy)
\el(\bx, \by)(\gx, \gy)
%\el(\cx, \cy)(\hx, \hy)
\el(\dx, \dy)(\ix, \iy)
%\el(\ex, \ey)(\jx, \jy)
\el(\fx, \fy)(\kx, \ky)
%\el(\gx, \gy)(\lx, \ly)
\el(\hx, \hy)(\mx, \my)
\el(\ix, \iy)(\nx, \ny)
%\el(\jx, \jy)(\ax, \ay)
\el(\kx, \ky)(\bx, \by)
%\el(\lx, \ly)(\cx, \cy)
\el(\mx, \my)(\dx, \dy)
%\el(\nx, \ny)(\ex, \ey)

%7 hosszu
%\el(\ax, \ay)(\hx, \hy)
\el(\bx, \by)(\ix, \iy)
%\el(\cx, \cy)(\jx, \jy)
\el(\dx, \dy)(\kx, \ky)
%\el(\ex, \ey)(\lx, \ly)
\el(\fx, \fy)(\mx, \my)
%\el(\gx, \gy)(\nx, \ny)

\put(-0.4, -1.6){Red edges}
\end{picture}}
\end{picture}
$$

\centerline{\bf Fig. 1}

\medskip


To see that this graph does not contain
$n$ pairwise non-crossing blue triangles, 
we need the following lemma that can be
proved by induction.
By an {\em arc} we mean a set of consecutive vertices.

\begin{lemma}\label{6.1}
{\it Suppose that an arc $I$ of $m\le n/2$ vertices
contains the vertices of $h$ pairwise non-crossing blue triangles. Then 
$m\ge 7h-1$. Moreover, if $m=7h-1$, then the starting point
of $I$ is blue.}

\end{lemma}

Consider a maximal set of pairwise non-crossing blue triangles.
Suppose first that the points can be 
partitioned into three arcs, $I_1,I_2,I_3$, 
with $m_i=|I_i|\le n/2$ such that the vertices of 
each of these triangles belong to the same arc.
Let $k_i$ denote the number of triangles whose vertices belong to $I_i$.
By Lemma~\ref{6.1}, we have
$$7n-7=m_1+m_2+m_3 \ge (7k_1-1)+(7k_2-1)+(7k_3-1)>7(k_1+k_2+k_3)-7,$$
\noindent and we can conclude that $k_1+k_2+k_3<n$.

Otherwise, there is a blue triangle so that the convex hull of its vertex set 
contains the center of our regular $n$-gon.
Its vertices, $p,q,r$, partition the remaining set of points into three arcs of
lengths $m_1,m_2,m_3$ containing $k_1,k_2,k_3$ triangles, respectively. 
From Lemma~\ref{6.1} we obtain
$$7n-7=m_1+m_2+m_3+3 \ge (7k_1-1)+(7k_2-1)+(7k_3-1)+3=7(k_1+k_2+k_3),$$
\noindent implying $n\ge k=k_1+k_2+k_3+1$. 
Suppose that $n=k$. Then we have equality in the previous inequalities, 
therefore, the length of each side of
triangle $pqr$
is divisible by 7. On the other hand, by Lemma~\ref{6.1}, all of the points
$p+1,q+1,r+1$ are blue, so $pqr$ is  
a monochromatic
red triangle, a contradiction. 

The existence of $n$ non-crossing red triangles can be excluded 
by a similar argument.

\small

\begin{thebibliography}{DSS}

%\bibitem[AEG94]{AEG94}
%{B. Aronov, P. Erd\H os, W. Goddard, D. Kleitman, M. Klugerman, J. Pach,
%and L. Schulman,}
%{Crossing families,}
%{\it Combinatorica} {\bf 14} (1994), 127--134.

\bibitem[AGHN97]{AGHN97}
{M. Abellanas, J. Garc\'{\i}a, G. Hern\'andez, M. Noy, and P. Ramos,}
{Bipartite embeddings of trees in the plane,}
in: {\it Graph Drawing '96 (S. North, ed.), Lecture Notes in Computer Science}
{\bf 1190}, Springer, Berlin, 1997, 1--10.


%\bibitem[ARR93]{ARR93}
%{N. Alon, S. Rajagopalan, and S. Suri,}
%{Long Non-Crossing Configurations in the Plane,}
%in: {\it Proc. of the 9th Annual Symposium on Computational Geometry,}
%ACM Press, 1987, 257--263.


%\bibitem[B83]{B83}
%{J. Beck,}
%{On size Ramsey number of paths, trees, and circuits, I.,}
%{\it Journal of Graph Theory} {\bf 7} (1983), 115--129.

%\bibitem[BCG82]{BCG82}
%{E. R. Berlekamp, J. H. Conway, and R. K. Guy,}
%{\it Winning Ways, Vol. 2.}
%Academic Press, London, 1982.

%\bibitem[BD91]{BD91}
%{A. Bialostocki and P. Dierker,}
%{On simple Hamiltonian cycles in a 2--colored complete graph,}
%{\it Ars Combinatoria} {\bf 32} (1991), 13--16.

%\bibitem[BD94]{BD94}
%{A. Bialostocki and P. Dierker,}
%{Personal communication.}

\bibitem[B74]{B74}
{S.A. Burr,}
{Generalized Ramsey theory for graphs -- a survey,}
in: {\it Graphs and Combinatorics (R. Bari and F. Harary, eds.),
Lecture Notes in Mathematics} {\bf 406}, Springer--Verlag, Berlin,
1974, 52--75.

\bibitem[BES75]{BES75}
{S.A. Burr, P. Erd\H os, and J.H. Spencer,}
{Ramsey theorems for multiple copies of graphs,}
{\it Transactions of the American Mathematical Society} {\bf 209} (1975),
87--99.

\bibitem[D50]{D50}
{R.P. Dilworth,}
{A decomposition theorem for partially ordered sets,}
{\it Annals of Mathematics} {\bf 51} (1950), 161--166.

%\bibitem[EFR78]{EFR78}
%{P. Erd\H os, R.J. Faudree, C.C. Rousseau, and R.H. Schelp,}
%{The size Ramsey number,}
%{\it Periodica Mathematica Hungarica} {\bf 9} (1978), 145--161.

%\bibitem[EG95]{EG95}
%{P. Erd\H os and A. Gy\'arf\'as,}
%{Vertex covering with monochromatic paths,}
%{\it Mathematica Pannonica} {\bf 6} (1995), 7--10.

%\bibitem[EGP91]{EGP91}
%{P. Erd\H os, A. Gy\'arf\'as, and L. Pyber,}
%{Vertex coverings by monochromatic cycles and trees,}
%{\it Journal of Combinatorial Theory, Series B} {\bf 51} (1991), 90--95.

\bibitem[ELSS73]{ELSS73}
{P. Erd\H os, L. Lov\'asz, A. Simmons, and E.G. Straus,}
{Dissection graphs of planar point sets,}
in: {\it A Survey of Combinatorial Theory (G. Srivastava, ed.),}
North--Holland, Amsterdam, 1973, 139--149.

%\bibitem[GG67]{GG67}
%{L. Gerencs\'er and A. Gy\'arf\'as,}
%{On Ramsey--type problems,}
%{\it Annales Universitatis Scientarium Budapestinensis Roland
%E\"otv\"os, Sectio Mathematica} {\bf X} (1967), 167--170.

\bibitem[GMPP91]{GMPP91}
{P. Gritzmann, B. Mohar, J. Pach, and R. Pollack,}
{Embedding a planar triangulation with vertices at specified points (solution
to problem E3341),}
{\it American Mathematical Monthly} {\bf 98} (1991), 165-166.

\bibitem[GRS90]{GRS90}
{R.L. Graham, B.L. Rothschild, and J.H. Spencer,}
{\it Ramsey Theory, 2nd ed.,} John Wiley, New York, 1990.

%\bibitem[G83]{G83}
%{A. Gy\'arf\'as,}
%{Vertex coverings by monochromatic paths and cycles,}
%{\it Journal of Graph Theory} {\bf 7} (1983), 131--135.

%\bibitem[G89]{G89}
%{A. Gy\'arf\'as,}
%{Covering complete graphs by monochromatic paths,}
%in: {\it Irregularities of Partitions (G. Hal\'asz and V.T. S\'os, eds.),
%Algorithms and Combinatorics} {\bf 8}, Springer--Verlag, Heidelberg,
%1989, 89--91.

%\bibitem[HS92]{HS92}
%{J. Hershberger and S. Suri,}
%{Applications of a semidynamic convex hull algorithm,}
%{\it BIT} {\bf 32} (1992), 249-267.


%\bibitem[HKS87]{HKS87}
%{A. Hajnal, P. Komj\'ath, L. Soukup, and I. Szalkai,}
%{Decompositions of edge colored infinite complete graphs,}
%in: {\it Combinatorics, Colloquia Mathematica Societatis J\'anos Bolyai}
%{\bf 52} (1987), 277--280.

%\bibitem[K97]{K97}
%{Gy. K\'arolyi,}
%{Disjoint monochromatic triangles in complete 2-colored geometric graphs,}
%submitted to {\it Discrete Mathematics}.

\bibitem[KPT96]{KPT96}
{Gy. K\'arolyi, J. Pach, and G. T\'oth,}
{Ramsey--type results for geometric graphs. I,}
in: {\it Proceedings of the 12th Annual ACM Symposium on
Computational Geometry} 1996, 359-365. Also in:
{\it Discrete and Computational Geometry,}
to appear.

\bibitem[KPTT97]{KPTT97}
{Gy. K\'arolyi, J. Pach, G. Tardos, and G. T\'oth,}
{An algorithm for finding many disjoint monochromatic edges in a complete
2-colored geometric graph,}
in: {\it Intuitive Geometry,
(I. B\'ar\'any, K. B\"or\"oczky, eds.), Bolyai Soc. Math. Studies} {\bf 6}, 
to appear.

%\bibitem[LMP94]{LMP94}
%{D.G. Larman, J. Matou\v sek, J. Pach, and J. T\"or\H ocsik,}
%{A Ramsey--type result for planar convex sets,}
%{\it Bulletin of the London Mathematical Society} {\bf 26} (1994), 132--136.

%\bibitem[MP93]{MP93}
%{W. Moser and J. Pach,}
%{Recent Developments in Combinatorial Geometry,}
%in: {\it New Trends in Discrete and Computationial Geometry, (J. Pach, ed.),}
%Springer--Verlag, Berlin, 1993, 281--302.

\bibitem[PA95]{PA95}
{J. Pach and P.K. Agarwal,}
{\it Combinatorial Geometry,}
John Wiley, New York, 1995.

%\bibitem[R78]{R78}
%{R. Rado,}
%{Monochromatic paths in graphs,}
%in: {\it Advances in Graph Theory (B. Bollob\'as, ed.), Annals of Discrete
%Mathematics} {\bf 3}, North--Holland, Amsterdam, 1978, 191--194.

\end{thebibliography}





\end{document}















