Monotonic subsequences in dimensions higher than one (Q1378553)

Summary: The 1935 result of Erdős and Szekeres that any sequence of \(\geq n^2 +1\) real numbers contains a monotonic subsequence of \(\geq 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 \(\leq n^{1/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 \(\sim 2n^{1/2}\) as \(n \to \infty\) for each dimension.