Combinatorics, Probability and Computing

Research Article

A Ramsey-Type Theorem in the Plane

Jaroslav Nešetřila1 and Pavel Valtra2

a1 Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic

a2 Graduiertenkolleg ‘Algorithmische Diskrete Mathematik’, Fachbereich Mathematik, Freie Universität Berlin, Takustrasse 9, 14195 Berlin, Germany

Abstract

We show that, for any finite set P of points in the plane and for any integer k ≥ 2, there is a finite set R = R(P, k) with the following property: for any k-colouring of R there is a monochromatic set , R, such that is combinatorially equivalent to the set P, and the convex hull of P contains no point of R \ . We also consider related questions for colourings of p-element subsets of R (p > 1), and show that these analogues have negative solutions.

(Received October 01 1993)

(Revised November 05 1993)

Footnotes

The author was supported by ‘Deutsche Forschungsgemeinschaft’, grant We 1265/2–1.