## Monotone Subsequences in Rd

###
Laura Heinrich-Litan

Institut für Informatik

Freie Universität Berlin

Takustr. 9, D-14195 Berlin

email: *litan*@inf.fu-berlin.de

Report B-00-19

December 2000

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 Rd=&\lt:,&\gt:^d, with other words
if it is monotone in each dimension i E {1,...,d}.
The main result of this paper is the construction of a set P
which has no monotone subsequences of length larger then
| n^{½:^{d-1}}|.
This generalizes to higher dimensions the Erdös-Szekeres result
that there is a 2-dimensional set of n points
which has monotone subsequences of length at most | \sqrt{n}|.
Get the report here or by anonymous ftp:
Server: ftp.inf.fu-berlin.de
File: pub/reports/tr-b-00-19.ps.gz