×

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.

MSC:

05A05 Permutations, words, matrices
06A07 Combinatorics of partially ordered sets
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: EuDML EMIS