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