| 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$.
|