Ramsey-Remainder


Pavel Valtr
Department of Applied Mathematics
Charles University
Czech Republic
email: valtr@CSPGUK11.bitnet
Report B 93-01
February 93

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-93-01.ps.gz

We investigate the following Ramsey-type problem. Given a natural number $k,$ determine the smallest integer $rr(k)$ such that, if $n$ is sufficiently large with respect to $k,$ and $S$ is any set of $n$ points in general position in the plane, then all but at most $rr(k)$ points of $S$ can be partitioned into convex sets of sizes $\ge k.$ We provide estimates on $rr(k)$ which are best possible if a classic conjecture of Erd\H{o}s and Szekeres on the Ramsey number for convex sets is valid. We also prove that in many types of combinatorial structures, the corresponding ``Ramsey-remainder'' $rr(k)$ is equal to the off-diagonal Ramsey number $r(k,k-1)$ minus $1.$

Ramsey-Remainder

Pavel Valtr Department of Applied Mathematics Charles University Czech Republic email: valtr@CSPGUK11.bitnet Report B 93-01 February 93