Monotonic subsequences in dimensions higher than one

Abstract

The 1935 result of Erdos and Szekeres that any sequence of ≥ n 2 + 1 real numbers contains a monotonic subsequence of ≥ n + 1 terms has stimulated extensive further 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 exist sequences of n points in the plane for which the longest monotonic subsequences have length ≤ n1/2 + 3. Weaker results are obtained for higher dimensions. When points are selected at random from reasonable distributions, the average length of the longest monotonic subsequence is shown to be ∼2n1/2 as n → ∞ for each dimension.