Monotonic subsequences in dimensions higher than one (Q1378553)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Monotonic subsequences in dimensions higher than one
scientific article

    Statements

    Monotonic subsequences in dimensions higher than one (English)
    0 references
    15 February 1998
    0 references
    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.
    0 references
    monotonic subsequence
    0 references
    Kruskal's conjecture
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references