Monotonic subsequences in dimensions higher than one
type: Item
instance of: scholarly article
title: Monotonic subsequences in dimensions higher than one
zbMATH Open document ID: 0884.05001
published in: The Electronic Journal of Combinatorics
publication date: 1998-02-15T00:00:00Z
full work available at URL: https://eudml.org/doc/119209
full work available at URL: v4i2r14ab.html
review text: 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.
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 1118081
zbMATH Keywords: monotonic subsequence
zbMATH Keywords: Kruskal's conjecture
author: Andrew Odlyzko
author: James B. Shearer
author: Ryan Siders
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1118081