Abstract : The Erdos-Szekeres convex polygon theorem asserts that among sufficiently many points, in general position in the plane, one can always find the vertices of a convex $n$-gon. In this talk we survey some results and intriguing open problems related to this theorem, and study in detail the following problem:

Let $f(k, n)$, $n\ge k\ge 3$, denote the smallest positive integer such that any set of $f(k, n)$ points, in general position in the plane, contains $n$ points whose convex hull has at least $k$ vertices.

The study of this function was motivated by a problem of Joe Mitchell concerning partition of point sets into (the vertex sets of) convex quadrilaterals, a question related to quadrangular mesh generation. We give lower and upper estimates on $f(k, n)$, both in the form $c_1kn+2^{c_2k}$, obtained together with Geza Toth.