Title  Monotone Subsequences in Rd.  

Author  Laura Heinrich-Litan.  

Abstract  This paper investigates the length of the longest monotone subsequence of a set of n points in Rd. A sequence of points in Rd is called monotone in Rd if it is monotone with respect to some order from ${\cal R}_{d}=\{\leq,\geq\}^d$, with other words if it is monotone in each dimension $i\in \{1,\ldots,d\}$. The main result of this paper is the construction of a set P which has no monotone subsequences of length larger then $\lceil n^{\frac{1}{2^{d-1}}}\ \rceil$. This generalizes to higher dimensions the Erdos-Szekeres result that there is a 2-dimensional set of n points which has monotone subsequences of length at most $\lceil\sqrt{n}\ \rceil$.  

Downloading  [ps] [pdf]