Monotonic subsequences in dimensions higher than one

A. M. Odlyzko, J. B. Shearer, R. Siders

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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.

Original languageEnglish (US)
Article numberR14
Pages (from-to)1-8
Number of pages8
JournalElectronic Journal of Combinatorics
Volume4
Issue number2 R
StatePublished - Dec 1 1997

Fingerprint Dive into the research topics of 'Monotonic subsequences in dimensions higher than one'. Together they form a unique fingerprint.

Cite this