Monotonic subsequences in dimensions higher than one.

Abstract

The 1935 result of Erdos and Szekeres that any sequence of at least $n^{2}+1$ real numbers contains a monotonic subsequence of at least $n+1$ terms has stimulated extensive furher research, including a paper of J.B.Kruskal that defined an extension of monotonicity for higher dimensions. This paper provides a proof of a weakened form of Kruskal's conjecture for 2 dimensional Euclidean space by showing that there exists a sequence of n points in the plane for which the longest monotonic subsequences have length $n^{2}+2$ or less.. Weaker results are also obtained for higher dimensions. The average length of the longest increasing monotonic subsequence is shown to be $\sim 2n^{1/2}$ as $n\rightarrow\infty$ for each dimension.