On the Erdős-Szekeres Problem for Convex Permutations and Orthogonally Convex Point Sets

Abstract

A finite set of points is generic if no two points are on the same vertical or horizontal line. The set is orthogonally convex if every point has an empty quadrant. We study the smallest integer $N_o(n)$ such that every generic set of $N_o(n)$ points contains a orthogonally convex subset of size $n$. For even $n$, we prove $N_0(n) = \frac{1}{8}(n^2+2n+8)$, which is tight, and in the odd case we get close upper and lower bounds. To prove these results, we apply the theory of Greene and Kleitman (1976) and Frank (1980) about posets to the partial order of point sets in the plane. Generic sets correspond to permutations in a canonical way.

A permutation is convex if it is order isomorphic to a finite generic set of points in convex position. The value of $N_o(n)$ is also the smallest $N$ such that every permutation of $N$ contains a convex subpermutation of size $n$.