The Partitioned Version of the Erd?s—Szekeres Theorem

   Abstract. Let k≥ 4 . A finite planar point set X is called a convex k -clustering if it is a disjoint union of k sets X ₁ , . . . ,X _k of equal sizes such that x ₁ x ₂ . . . x _k is a convex k -gon for each choice of x ₁ ∈ X ₁ , . . . ,x _k ∈ X _k . Answering a question of Gil Kalai, we show that for every k≥ 4 there are two constants c=c(k) , c'=c'(k) such that the following holds. If X is a finite set of points in general position in the plane, then it has a subset X' of size at most c' such that X \ X' can be partitioned into at most c convex k -clusterings. The special case k=4 was proved earlier by Pór. Our result strengthens the so-called positive fraction Erdos—Szekeres theorem proved by Barany and Valtr. The proof gives reasonable estimates on c and c' , and it works also in higher dimensions. We also improve the previous constants for the positive fraction Erdos—Szekeres theorem obtained by Pach and Solymosi.