Monotone Subsequences in Rd

Laura Heinrich-Litan
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin

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:
File:   pub/reports/