Odlyzko, A. M.; Shearer, J. B.; Siders, R. Monotonic subsequences in dimensions higher than one. (English) Zbl 0884.05001 Electron. J. Comb. 4, No. 2, Research paper R14, 8 p. (1997); printed version J. Comb. 4, No. 2, 173-181 (1997). 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. Cited in 1 Document MSC: 05A05 Permutations, words, matrices 06A07 Combinatorics of partially ordered sets 60C05 Combinatorial probability Keywords:monotonic subsequence; Kruskal’s conjecture PDFBibTeX XMLCite \textit{A. M. Odlyzko} et al., Electron. J. Comb. 4, No. 2, Research paper R14, 8 p. (1997; Zbl 0884.05001) Full Text: EuDML EMIS