A Ramsey-type theorem in the plane
Pavel Valtr (joint work with Jaroslav Nesetril)
Department of Applied Mathematics
Charles University
Czech Republic
email: valtr@CSPGUK11.bitnet
Report B 94-03
January 94
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-94-03.ps.gz
We show that for any finite set $P$ of points
in the plane and for any integer $k\ge2$
there is a finite set $R=R(P,k)$ with the following property:
For any $k$-colouring of $R$
there is a monochromatic set $\ppp,\ppp\subseteq R,$ such that
$\ppp$ is combinatorially equivalent to the set $P$ and
the convex hull of $\ppp$ contains no point of $R\setminus\ppp.$
We also consider related questions for colourings of $p$-element
subsets of $R$ ($p>1$) and
show that these analogues have negative solutions.